题解：Car的旅行路线

口胡五分钟，代码两小时！

这个题啊，真是好写，也不好写。

好写呢，在于建个图，再跑一遍 $Floyd$ ，比较最小值，就没了

不好写呢，就在于：

1.每个矩形只给了3个点.....

2.代码长（可能不是），相近的变量多（这是我）等等

来一步一步分析吧。。。

$0.$ 题意:

~~（略）~~

$1.$ 建图

$(1).$ 找到矩形的另外 $1$ 个点

这个东西咋找呢？用亿点初中几何知识知道矩形是平行四边形，而平行四边形是对角线互相平分的。

如图所示：

其中，点 $A,B,C$ 为输入的点， $D$ 是所求的点，对角线交点为 $P$

这个例子中， $BC$ 是一条对角线， $AD$ 是另一条。根据中点公式，可以得到

$\begin{cases}x_P=\dfrac{x_B+x_C}{2}\\x_P=\dfrac{x_A+x_D}{2}\end{cases}$

$\begin{cases}y_P=\dfrac{y_B+y_C}{2}\\y_P=\dfrac{y_A+y_D}{2}\end{cases}$

所以可得

$\begin{cases}x_D=x_B+x_C-x_A\\y_D=y_B+y_C-y_A\end{cases}$

于是，我们再用勾股定理判断一下哪两个点构成对角线，然后就能求出这个点啦！

$(2).$ 建图

这里我们发现题目给了两种路线，一种是城市之间的航空路线，一种是城市内部的公路。

所以建图的主要问题就在于判断两个点是否在同一城市内。

这个问题，要靠你标点的方式确定，此处就举本人的例子来说明。

我的想法是第 $1$ 个城市标号 $1,2,3,4$ ,第 $2$ 个城市标号 $5,6,7,8$ ,以此类推。

那么这些点的标号与对应的城市号有什么关系呢？

经过研究发现，若点的编号为 $i$ ,则它对应的城市编号即为 $(i-1)/4$ （下取整）

于是这样就行了。

$2.$ 最短路

$emmm$ ，一看数据范围， $s \leq 100$

所以最多只有 $400$ 个点， $O(n^3)$ 都能过。

那么 $O(n^3)$ 的最短路是啥？ $Floyd$ 啊~

跑一遍 $Floyd$ ，然后求一下 $A$ 的每个机场到 $B$ 的每个机场的最小值就过了~

完整代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i,a,b) for(int i=a;i<=b;i++)
const ll inf=0x7f7f7f7f;
ll s,A,B,TTT;
double ans=inf,t,dis[410][410];
double x[410],y[410],T[110];
double diss(double x1,double y1,double x2,double y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
double ds(double x1,double y1,double x2,double y2){return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);}
int main() {
    scanf("%lld",&TTT);
    while(TTT--){
        memset(dis,0,sizeof(dis)),ans=inf;
        scanf("%lld%lf%lld%lld",&s,&t,&A,&B);
        f(i,1,s){
            scanf("%lf%lf%lf%lf%lf%lf%lf",&x[(i-1)*4+1],&y[(i-1)*4+1],&x[(i-1)*4+2],&y[(i-1)*4+2],&x[(i-1)*4+3],&y[(i-1)*4+3],&T[i]);
            double dab=ds(x[(i-1)*4+1],y[(i-1)*4+1],x[(i-1)*4+2],y[(i-1)*4+2]);
            double dac=ds(x[(i-1)*4+1],y[(i-1)*4+1],x[(i-1)*4+3],y[(i-1)*4+3]);
            double dbc=ds(x[(i-1)*4+2],y[(i-1)*4+2],x[(i-1)*4+3],y[(i-1)*4+3]);
            if(dab+dac==dbc)x[i*4]=x[(i-1)*4+2]+x[(i-1)*4+3]-x[(i-1)*4+1],y[i*4]=y[(i-1)*4+2]+y[(i-1)*4+3]-y[(i-1)*4+1];else
            if(dab+dbc==dac)x[i*4]=x[(i-1)*4+1]+x[(i-1)*4+3]-x[(i-1)*4+2],y[i*4]=y[(i-1)*4+1]+y[(i-1)*4+3]-y[(i-1)*4+2];else
            if(dbc+dac==dab)x[i*4]=x[(i-1)*4+2]+x[(i-1)*4+1]-x[(i-1)*4+3],y[i*4]=y[(i-1)*4+2]+y[(i-1)*4+1]-y[(i-1)*4+3];
        }
        f(i,1,s*4)f(j,1,s*4)if(i!=j){
                if((i-1)/4!=(j-1)/4)dis[i][j]=t*diss(x[i],y[i],x[j],y[j]);
                else dis[i][j]=T[(i-1)/4+1]*diss(x[i],y[i],x[j],y[j]);
            }
        f(k,1,s*4)f(i,1,s*4)f(j,1,s*4)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
        f(i,1,4)f(j,1,4)ans=min(ans,dis[(A-1)*4+i][(B-1)*4+j]);
        printf("%.1lf\n",ans);
    }
    return 0;
}