记录编号 581196 评测结果 AAAAA
题目名称 [NOIP 2001]Car的旅行路线 最终得分 100
用户昵称 Gravatar宇战 是否通过 通过
代码语言 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;
}