题解 P1027 【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;
}