[위 키 오 이] 1041 Car 의 여행 코스.

제목 링크
알고리즘: 최 단 로 (데이터 가 약 하고 Floyd 도 통과 할 수 있 습 니 다)
뼈 아 픈 교훈: 이 문 제 를 적어도 20 번 은 제출 했 습 니 다. 그 이 유 는 = 너무 경솔 하고 부주의 하기 때 문 입 니 다. 그 몇 조 의 데 이 터 를 보고 도시 의 수량 이 라 고 생각 하여 배열 이 작 게 열 렸 습 니 다.(미안 하 다, 위 키 오 이의 평가 기 = =).운행 오 류 를 계속 보고 하 다.나 는 뜻밖에도 줄곧 경 계 를 넘 었 다 는 것 을 알 아내 지 못 했다.
기억 하기: 데이터 범 위 를 잘 봐 야 지 아아 아!!!!!
이 문제 에서 가장 징 그 러 운 것 은 네 번 째 노드 를 처리 하 는 것 이다. 처음에 나 는 네 번 째 점 (본인 은 33951 점, 33979 점) 을 어떻게 계산 해 야 할 지 몰 랐 다. 단순 한 x4 = x1 + x2 - x3 이면 지나 갈 수 있다 고 생각 했다.근 데 안 돼.뒤에 문 제 를 봤 는데 직각 변 종점 x1, y1 과 x2, y2 일 거 예요.그 러 니까 어느 쪽 이 직각 변 인지 판단 해 야 돼.
하면, 만약, 만약... (x1 - x2) * (x3 - x2) + (y1 - y2) * (y3 - y2) = 0, 그러면 L1 은 88692 입 니 다.
아 픈 코드:

#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
";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;

}