白井黑子洛谷傳送服務
白井黑子vijos傳送服務
今天，是個重大一天，因為從今天起，為了大家有更好的體驗，我将對我的題解進行全新改版！！
（不滿的lovechq：你不就還有5天就去備戰聯考了嗎？現在改版有啥用？
來自cgg的答複：雖然，在過幾天，我會和大家依依不舍道地别，因為我真的要去備戰聯考了，但是明年暑假我會強勢回歸的！請各位放心）
知識點
（cgg解釋：這裡是為了讓大家看到此題涉及的知識點，可以提前預習）
計算幾何
向量，兩點間距離公式
圖論
鄰接矩陣、Floyd（最短路）
基本思路
（cgg解釋：這個版塊是為了有些巨神準備的，因為巨神有時候隻是一時短路，隻要簡單看看思路就可以了，是以在這裡把思路簡單整理一下，便于檢視）
用資料結構去儲存城市和點。
用向量求第四個點。
然後建圖，算出每兩個點之間的花費。
Floyd
詳細解釋
（cgg解釋：這個版塊是解釋上面沒有說清楚的地方）
儲存城市和點
我們可以寫兩個結構體，一個是點，一個是城市。
計算第四個點
我們先來看看怎麼計算第四個點。
我們可以先計算出來已知的三個點兩兩之間的距離，由于是矩形，我們一定有一個斜邊，也就是矩形的對角線，也就是我們求出的三個距離中最長的那一個
那麼接下來怎麼處理呢？
我們來看一個圖：
其中ABC三點已知。
我們觀察向量BC和向量AD（你不知道向量？快戳開）
因為四邊形ABCD是矩形，是以向量BC和向量AD應該相等。
是以(x3-x2,y3-y2)=(x4-x1,y4-y1)
是以我們就可以求出來第四個點了：
x4=x3+x1-x2
y4=y3+y1-y2
這樣就大功告成了！
建圖計算距離
計算距離就用兩點間距離公式
然後注意枚舉順序，依次計算出每一個點到同一個城市其他點的花費，再計算到其他城市每一個點的花費。
注意不隻是距離，還要乘上每機關長度的花費。
用鄰接矩陣就好了
Floyd
最簡單的最短路算法，就不說了。
最後隻要對起始和終點城市的每個飛機場之間的距離進行枚舉，得到最小值即可。
難度點評
（cgg解釋：客觀地評價）
不是很難，沒有什麼思維難度，重在考察代碼能力。
代碼
（cgg解釋：這顯然是題解不可少的一部分）
！！！請注意：vijos的題目和洛谷的不一樣
本處隻提供洛谷的代碼
vijos的題目沒有多組資料，且保留兩位小數
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
struct point{
int num;
int x,y;
};
struct city{
point poi[];
int w;
};
int T;
int n,t,A,B;
city c[];
int ind;
double mapp[][];
double dis(point poi1,point poi2){
return sqrt((poi1.x-poi2.x)*(poi1.x-poi2.x)+(poi1.y-poi2.y)*(poi1.y-poi2.y));
}
void getpoi4(city& ci){
double l12=dis(ci.poi[],ci.poi[]),l13=dis(ci.poi[],ci.poi[]),l23=dis(ci.poi[],ci.poi[]);
if(l12>l13&&l12>l23){
ci.poi[].x=ci.poi[].x+ci.poi[].x-ci.poi[].x;
ci.poi[].y=ci.poi[].y+ci.poi[].y-ci.poi[].y;
}else if(l13>l12&&l13>l23){
ci.poi[].x=ci.poi[].x+ci.poi[].x-ci.poi[].x;
ci.poi[].y=ci.poi[].y+ci.poi[].y-ci.poi[].y;
}else{
ci.poi[].x=ci.poi[].x+ci.poi[].x-ci.poi[].x;
ci.poi[].y=ci.poi[].y+ci.poi[].y-ci.poi[].y;
}
}
int main(){
scanf("%d",&T);
ind=;
while(T--){
memset(mapp,,sizeof(mapp));
scanf("%d%d%d%d",&n,&t,&A,&B);
for(int i=;i<=n;i++){
scanf("%d%d%d%d%d%d%d",&c[i].poi[].x,&c[i].poi[].y,&c[i].poi[].x,&c[i].poi[].y,&c[i].poi[].x,&c[i].poi[].y,&c[i].w);
getpoi4(c[i]);
c[i].poi[].num=ind++;
c[i].poi[].num=ind++;
c[i].poi[].num=ind++;
c[i].poi[].num=ind++;
}
for(int i=;i<=n;i++){
for(int j=;j<=4;j++){
point cur=c[i].poi[j];
for(int k=j+;k<=4;k++){
point kkk=c[i].poi[k];
mapp[cur.num][kkk.num]=mapp[kkk.num][cur.num]=dis(cur,kkk)*(double)c[i].w;
}
for(int k=i+;k<=n;k++){
for(int l=;l<=4;l++){
point kkk=c[k].poi[l];
mapp[cur.num][kkk.num]=mapp[kkk.num][cur.num]=dis(cur,kkk)*(double)t;
}
}
}
}
for(int k=;k<ind;k++){
for(int i=;i<ind;i++){
for(int j=;j<ind;j++){
if(i==j){
mapp[i][j]=;
continue;
}
mapp[i][j]=min(mapp[i][j],mapp[i][k]+mapp[k][j]);
}
}
}
double ans=;
for(int i=;i<=4;i++){
for(int j=;j<=4;j++){
ans=min(ans,mapp[c[A].poi[i].num][c[B].poi[j].num]);
}
}
printf("%.1lf\n",ans);
}
return ;
}