【wikioi】1041 Car的旅行路線

題目連結

算法：最短路（資料弱，Floyd也能過）

慘痛的教訓：此題我至少送出了20次，原因在于= =太草率和粗心了，看到那個多少組資料以為是城市的數量，導緻數組開得小小的= =。（對不起，wikioi的評測機= =）。一直報運作錯誤。。我居然一直沒查到是越界= =TAT

記住：一定要看清資料範圍啊啊啊啊啊！！！！！

此題最惡心的是處理第四個節點，剛開始我不知道怎麼算第四個點（本人蒟蒻），以為單純的x4=x1+x2-x3就可以過。。。可是不行。後面是看了題解的，應該是直角邊終點x1，y1和x2，y2。是以要判斷哪個是直角邊。

對于線段L1、L2，如果（x1-x2）*（x3-x2）+（y1-y2）*（y3-y2）＝0,那麼L1 ⊥ L2。

上慘痛的代碼：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <cmath>
using namespace std;
const double oo = 10000000;
//城市的飛機場 (x-1)*4+1代表第x個城市開始的飛機場下标
#define CTOA(x) (((x-1)<<2)+1)
//距離
#define DISTANCE(x1,y1,x2,y2) ((double)sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)))
//此題我用FLOYD做的，因為資料太弱，過了
//每個飛機場為一個節點，答案就是A到B所有的路線最短路的最小值
struct city
{
	int x[4], y[4];
}ct[105];

double node[4050][4050];
double T;
int s, t, A, B, N, i, j, k, l, temp, airport, tx[3], ty[3];
//至于計算第四個點，由數學知識我們可以知道，互相垂直的兩條直線的斜率互為負倒數，是以我們隻要每次計算AB、BC的斜率。
//如果不滿足條件，那麼将A、B、C的坐标分别指派為B、C、A，這樣不斷疊代，直到AB、BC垂直，這樣就能計算出第四個點的坐标。
//還要注意一個問題，如果AB或者BC與坐标軸垂直，需要單獨讨論這種情況，因為被除數不能為零。
//（１） 首先判斷直角的位置：
//因為從測試資料檔案中讀入的三個點的坐标是無序的，是以需判斷直角的位置，然後在計算第四個點的坐标。
//對于線段L1、L2，如果（x1-x2）*（x3-x2）+（y1-y2）*（y3-y2）＝0,那麼L1 ⊥ L2。
//（２） 計算（x4，y4）:
//由x4-x3＝x1-x2得x4＝x1-x2+x3，同樣的y4＝y1-y2+y3
void getfour(int c) //擷取第四個城市
{
	memcpy(tx, ct[c].x, sizeof(tx));
	memcpy(ty, ct[c].y, sizeof(ty));
	int tt;
	while((tx[0]-tx[1])*(tx[2]-tx[1])+(ty[0]-ty[1])*(ty[2]-ty[1]))
	{
		tt = tx[0]; tx[0]=tx[1]; tx[1]=tx[2]; tx[2]=tt;
		tt = ty[0]; ty[0]=ty[1]; ty[1]=ty[2]; ty[2]=tt;
	}
	ct[c].x[3] = tx[0]-tx[1]+tx[2];
	ct[c].y[3] = ty[0]-ty[1]+ty[2];}

int main()
{
	cin >> N;
	while(N--)
	{
		cin >> s >> t >> A >> B;
		//注意A=B的情況，也就是出發的城市就是結束的城市，這是要直接輸出‘0.0’；
		if(A == B) {cout << "0.0\n";continue;}
		//s<<2表示飛機場數量，即s*4
		airport = s << 2;
		for(i = 1; i <= airport; i++)
			for(j = 1; j <= airport; j++)
				node[i][j] = oo; //初始化

		for(i = 1; i <= s; i++)
		{
			for(j = 0; j < 3; j++)
				cin >> ct[i].x[j] >> ct[i].y[j];
			cin >> T;
			getfour(i);
			//初始同一城市飛機場的花費
			for(j = 0; j < 4; j++)
				for(k = 0; k < 4; k++)
					if(j != k)
						node[CTOA(i)+j][CTOA(i)+k] = DISTANCE(ct[i].x[j], ct[i].y[j], ct[i].x[k], ct[i].y[k]) * T;
		}

		//初始不同城市飛機場的花費
		for(i = 1; i <= s; i++)
			for(j = 1; j <= s; j++)
				if(i != j)
					for(k = 0; k < 4; k++)
						for(l = 0; l < 4; l++)
							node[CTOA(i)+k][CTOA(j)+l] = (DISTANCE(ct[i].x[k], ct[i].y[k], ct[j].x[l], ct[j].y[l]) * t);

		//Floyd
		for(k = 1; k <= airport; k++)
			for(i = 1; i <= airport; i++)
				for(j = 1; j <= airport; j++)
					node[i][j] = min(node[i][j], node[i][k]+node[k][j]);

		//A到B所有的路線最短路的最小值
		double ans = oo;
		for(i = 0; i < 4; i++)
			for(j = 0; j < 4; j++)
				ans = min(ans, node[CTOA(A)+i][CTOA(B)+j]);
		cout << setiosflags(ios::fixed) << setprecision(1) << ans << endl;
	}
	return 0;
}