| 记录编号 |
581196 |
评测结果 |
AAAAA |
| 题目名称 |
[NOIP 2001]Car的旅行路线 |
最终得分 |
100 |
| 用户昵称 |
 宇战 |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
0.000 s |
| 提交时间 |
2023-07-31 11:20:23 |
内存使用 |
0.00 MiB |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
double n,m,o,q[500][500],mm[500];
struct node{
double x1,y1,x2,y2,x3,y3,x4,y4,tt;
}d[100000];
void xie(int i){
double ii=sqrt((d[i].x1-d[i].x2)*(d[i].x1-d[i].x2)+(d[i].y1-d[i].y2)*(d[i].y1-d[i].y2));
double jj=sqrt((d[i].x1-d[i].x3)*(d[i].x1-d[i].x3)+(d[i].y1-d[i].y3)*(d[i].y1-d[i].y3));
double pp=sqrt((d[i].x2-d[i].x3)*(d[i].x2-d[i].x3)+(d[i].y2-d[i].y3)*(d[i].y2-d[i].y3));
if(ii>jj&&ii>pp){
d[i].x4=d[i].x1+d[i].x2-d[i].x3;
d[i].y4=d[i].y1+d[i].y2-d[i].y3;
}
if(jj>ii&&jj>pp){
d[i].x4=d[i].x1+d[i].x3-d[i].x2;
d[i].y4=d[i].y1+d[i].y3-d[i].y2;
}
if(pp>ii&&pp>jj){
d[i].x4=d[i].x2+d[i].x3-d[i].x1;
d[i].y4=d[i].y2+d[i].y3-d[i].y1;
}
}
void bian(int i){
double ii=sqrt((d[i].x1-d[i].x2)*(d[i].x1-d[i].x2)+(d[i].y1-d[i].y2)*(d[i].y1-d[i].y2));
double jj=sqrt((d[i].x1-d[i].x3)*(d[i].x1-d[i].x3)+(d[i].y1-d[i].y3)*(d[i].y1-d[i].y3));
double pp=sqrt((d[i].x2-d[i].x3)*(d[i].x2-d[i].x3)+(d[i].y2-d[i].y3)*(d[i].y2-d[i].y3));
double oo=sqrt((d[i].x1-d[i].x4)*(d[i].x1-d[i].x4)+(d[i].y1-d[i].y4)*(d[i].y1-d[i].y4));
double uu=sqrt((d[i].x2-d[i].x4)*(d[i].x2-d[i].x4)+(d[i].y2-d[i].y4)*(d[i].y2-d[i].y4));
double yy=sqrt((d[i].x3-d[i].x4)*(d[i].x3-d[i].x4)+(d[i].y3-d[i].y4)*(d[i].y3-d[i].y4));
q[(i-1)*4+1][(i-1)*4+2]=ii*d[i].tt;//12
q[(i-1)*4+1][(i-1)*4+3]=jj*d[i].tt;//13
q[(i-1)*4+1][(i-1)*4+4]=oo*d[i].tt;//14
q[(i-1)*4+2][(i-1)*4+3]=pp*d[i].tt;//23
q[(i-1)*4+2][(i-1)*4+4]=uu*d[i].tt;//24
q[(i-1)*4+3][(i-1)*4+4]=yy*d[i].tt;//34
///////////////////////////////////////////////
q[(i-1)*4+2][(i-1)*4+1]=ii*d[i].tt;//21
q[(i-1)*4+3][(i-1)*4+1]=jj*d[i].tt;//31
q[(i-1)*4+4][(i-1)*4+1]=oo*d[i].tt;//41
q[(i-1)*4+3][(i-1)*4+2]=pp*d[i].tt;//32
q[(i-1)*4+4][(i-1)*4+2]=uu*d[i].tt;//42
q[(i-1)*4+4][(i-1)*4+3]=yy*d[i].tt;//43
}
int main(){
freopen("cardlxlx.in","r",stdin);
freopen("cardlxlx.out","w",stdout);
cin>>o;
for(int p=1;p<=o;p++){
double s,t,a,b;
memset(q,0x3f,sizeof(q));
cin>>s>>t>>a>>b;
for(int i=1;i<=4*s;i++){
q[i][i]=0;
}
for(int i=1;i<=s;i++){
cin>>d[i].x1>>d[i].y1>>d[i].x2>>d[i].y2>>d[i].x3>>d[i].y3>>d[i].tt;
xie(i);
bian(i);
}
for(int i=1;i<=s;i++){
for(int k=1;k<=s;k++){
if(i==k)continue;
double ii=sqrt((d[i].x1-d[k].x2)*(d[i].x1-d[k].x2)+(d[i].y1-d[k].y2)*(d[i].y1-d[k].y2));
double jj=sqrt((d[i].x1-d[k].x3)*(d[i].x1-d[k].x3)+(d[i].y1-d[k].y3)*(d[i].y1-d[k].y3));
double pp=sqrt((d[i].x2-d[k].x3)*(d[i].x2-d[k].x3)+(d[i].y2-d[k].y3)*(d[i].y2-d[k].y3));
double oo=sqrt((d[i].x1-d[k].x4)*(d[i].x1-d[k].x4)+(d[i].y1-d[k].y4)*(d[i].y1-d[k].y4));
double uu=sqrt((d[i].x2-d[k].x4)*(d[i].x2-d[k].x4)+(d[i].y2-d[k].y4)*(d[i].y2-d[k].y4));
double yy=sqrt((d[i].x3-d[k].x4)*(d[i].x3-d[k].x4)+(d[i].y3-d[k].y4)*(d[i].y3-d[k].y4));
double gg=sqrt((d[i].x1-d[k].x1)*(d[i].x1-d[k].x1)+(d[i].y1-d[k].y1)*(d[i].y1-d[k].y1));
double hh=sqrt((d[i].x2-d[k].x2)*(d[i].x2-d[k].x2)+(d[i].y2-d[k].y2)*(d[i].y2-d[k].y2));
double vv=sqrt((d[i].x3-d[k].x3)*(d[i].x3-d[k].x3)+(d[i].y3-d[k].y3)*(d[i].y3-d[k].y3));
double bb=sqrt((d[i].x4-d[k].x4)*(d[i].x4-d[k].x4)+(d[i].y4-d[k].y4)*(d[i].y4-d[k].y4));
q[(i-1)*4+1][(k-1)*4+2]=ii*t;
q[(i-1)*4+1][(k-1)*4+3]=jj*t;
q[(i-1)*4+1][(k-1)*4+4]=oo*t;
q[(i-1)*4+2][(k-1)*4+3]=pp*t;
q[(i-1)*4+2][(k-1)*4+4]=uu*t;
q[(i-1)*4+3][(k-1)*4+4]=yy*t;
q[(k-1)*4+2][(i-1)*4+1]=ii*t;
q[(k-1)*4+3][(i-1)*4+1]=jj*t;
q[(k-1)*4+4][(i-1)*4+1]=oo*t;
q[(k-1)*4+3][(i-1)*4+2]=pp*t;
q[(k-1)*4+4][(i-1)*4+2]=uu*t;
q[(k-1)*4+4][(i-1)*4+3]=yy*t;
q[(i-1)*4+1][(k-1)*4+1]=gg*t;
q[(i-1)*4+2][(k-1)*4+2]=hh*t;
q[(i-1)*4+3][(k-1)*4+3]=vv*t;
q[(i-1)*4+4][(k-1)*4+4]=bb*t;
q[(k-1)*4+1][(i-1)*4+1]=gg*t;
q[(k-1)*4+2][(i-1)*4+2]=hh*t;
q[(k-1)*4+3][(i-1)*4+3]=vv*t;
q[(k-1)*4+4][(i-1)*4+4]=bb*t;
}
}
// for(int i=1;i<=s*4;i++){
// for(int j=1;j<=s*4;j++){
// cout<<q[i][j]<<' ';
// }
// cout<<endl;
// }
for(int k=1;k<=4*s;k++){
for(int i=1;i<=s*4;i++){
for(int j=1;j<=s*4;j++){
q[i][j]=min(q[i][j],q[i][k]+q[k][j]);
}
}
}
// cout<<q[1][2];
// for(int i=1;i<=s*4;i++){
// for(int j=1;j<=s*4;j++){
// cout<<q[i][j]<<' ';
// }
// cout<<endl;
// }
int top=0;
for(int i=1;i<=4;i++){
for(int j=1;j<=4;j++){
int uu=(a-1)*4+i;
int pp=(b-1)*4+j;
mm[++top]=q[uu][pp];
}
}
sort(mm+1,mm+1+top);
// cout<<mm[1];
printf("%.1lf\n",mm[1]);
}
return 0;
}