Car的旅行路线(Floyd+模拟)

题目地址

贼鸡儿猥琐的一道题

好在数据不毒瘤，而且Floyd就OK了。

这道题的难点在于建图，也很考验模拟能力，需要十分的有耐心。

建图

题目中告诉了我们一个矩形的三个点

我们在平面直角坐标系中随便画出一个直角三角形，假设(x1,y1)是直角的这个点，(x4,y4)是我们要求的第四个点，那么：

\[x_4=x_2+x_3-x_1,y_4=y_2+y_3-y_1
\]

（因为我画图太渣只好文字解说）

我们尝试在原直角三角形的基础上把整个矩形画出来，矩形的四个顶点分别平行于坐标轴做平行线，得到了一个平行于坐标轴的大矩形EFGH，发现这里面有一些全等三角形，你就能证明出上面的结论了。

Q：我们怎么知道哪个点是直角点呢？

A：利用勾股定理逆定理。

建图部分就这样解决了。

求解

暴力双精度小数Floyd。

Code

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cmath>

#define N 507

using namespace std;

inline int read() {

	int x=0,f=1; char ch=getchar();

	while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }

	while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }

	return x * f;

}

int n,s,t,A,B,cnt;

int T[N];

double g[N][N];

struct Point {

	int x,y,c;	//c就是哪个城市

}P[N];

inline int Dis(Point p1,Point p2) {

	return (p1.x-p2.x)*(p1.x-p2.x) + (p1.y-p2.y)*(p1.y-p2.y);	//为了方便计算，这个是距离的平方

}

void work() {

	cnt = 0;	//初始化

	s = read(), t = read(), A = read(), B = read();

	for(int i=1;i<=s;++i) {

		for(int j=1;j<=3;++j) {

			P[++cnt].x = read(), P[cnt].y = read(), P[cnt].c = i;

		}

		T[i] = read();

		int a = Dis(P[cnt-2],P[cnt-1]), b = Dis(P[cnt-2],P[cnt]), c = Dis(P[cnt-1],P[cnt]), x4, y4;

		int x1=P[cnt-2].x, x2=P[cnt-1].x, x3=P[cnt].x, y1=P[cnt-2].y, y2=P[cnt-1].y, y3=P[cnt].y;

		if(a+b == c) x4 = x2+x3-x1, y4 = y2+y3-y1;

		if(a+c == b) x4 = x1+x3-x2, y4 = y1+y3-y2;

		if(b+c == a) x4 = x1+x2-x3, y4 = y1+y2-y3;

		P[++cnt].x = x4, P[cnt].y = y4, P[cnt].c = i;

	}

	memset(g,0x3f,sizeof(g));

	for(int i=1;i<=4*s;++i) {

		for(int j=1;j<=4*s;++j) {

			if(i == j) continue;

			double dis = sqrt(Dis(P[i],P[j])), w = 0.0;

			if(P[i].c == P[j].c) {

				w = dis * (double)(T[P[i].c]);

			} else {

				w = dis * (double)(t);

			}

			g[i][j] = g[j][i] = w;

		}

	}

	for(int k=1;k<=4*s;++k) {

		for(int i=1;i<=4*s;++i) {

			for(int j=1;j<=4*s;++j) {

				g[i][j] = min(g[i][j], g[i][k]+g[k][j]);

			}

		}

	}

	double ans = 0x3f3f3f;

	for(int i=1;i<=4*s;++i) {

		for(int j=1;j<=4*s;++j) {

			if(P[i].c==A && P[j].c==B) {

				ans = min(ans, g[i][j]);

			}

		}

	}

	printf("%.1lf",ans);

}

int main()

{

	n = read();

	while(n--) {

		work();

	}

	return 0;

}

PS：这个人的题解质量越来越差了

巴特西

Car的旅行路线(Floyd+模拟)

题目地址

建图

求解

Code

最新文章

热门文章