专栏文章

题解：P1027 [NOIP 2001 提高组] Car 的旅行路线

RRetoayd
P1027题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip218no
此快照首次捕获于
2025/12/03 04:52
3 个月前
此快照最后确认于
2025/12/03 04:52
3 个月前
查看原文
这道题硬控我 11 小时。。。

题目难点：

主要是输入只告诉了我们三个点的坐标，所以需要求第四个点的坐标，要是每种情况都讨论一边的话代码比较长（但也能做），所以推荐写循环。剩下的就是最短路了，这里用 Floyd 就行了。

求第四点的方法：

初中数学中我们学到了两点间距离公式，中点公式和勾股定理，运用这三点，就能求出第四点的坐标了。
代码实现：
CPP
void work(int xx) {
	int ap, bp, cp; //cp代表直角三角形中斜边所对应的点，ap和bp代表另外两点
	for(int i = 0; i <= 2; i++) {
		for(int j = 0; j <= 2; j++) {
			for(int l = 0; l <= 2; l++) {
				if(i == j || j == l || i == l) continue;
				double ka = dis2(a[xx].x[i], a[xx].y[i], a[xx].x[j], a[xx].y[j]);
				double kb = dis2(a[xx].x[j], a[xx].y[j], a[xx].x[l], a[xx].y[l]);
				double kc = dis2(a[xx].x[i], a[xx].y[i], a[xx].x[l], a[xx].y[l]);
				if(ka + kb == kc) ap = l, bp = i, cp = j; //勾股定理判断是否构成直角三角形
				else continue;
			} 
		}
	}
	double midx = (a[xx].x[ap] + a[xx].x[bp]) / 2.0, midy = (a[xx].y[ap] + a[xx].y[bp]) / 2.0;
	midx *= 2, midy *= 2;
	newx = midx - a[xx].x[cp], newy = midy - a[xx].y[cp];
	return;
}
最重要的一点，这里求两点间距离的 dis2dis2 函数千万不要开根号，不然会有精度损失，导致没有答案。
dis2dis2 函数实现：
CPP
double dis2(double a1, double b1, double a2, double b2) {
    return (a1 - a2) * (a1 - a2) * 1.0 + (b1 - b2) * (b1 - b2) * 1.0;
 }

还有一个技巧：

除了 aa 数组存每一个城市的机场坐标以及里程费以外，再开一个数组 bb，保存每个机场的坐标以及从属的城市编号，这使后续操作方便许多。
就是这样：
CPP
struct Node { 
    double x[5], y[5], t;  
} a[N];

struct Nod { 
   int x, y, id;
} b[N];
这样，在最后求 AA 到 BB 城市的最少消耗时，就能够这样实现了（个人认为这样方便点）：
CPP
void print() {
	double res = 1000000000.0;
	for(int i = 1; i <= idx; i++) //idx表示机场个数
		for(int j = 1; j <= idx; j++)
			if(b[i].id == A && b[j].id == B)
				if(res > f[i][j]) res = f[i][j];
	printf("%.1lf\n", res);
}
最后，别忘了初始化做 Floyd 用的 ff 数组。

完整代码实现：

CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e2 + 5;

struct Node { double x[5], y[5], t;  } a[N];

struct Nod { int x, y, id; } b[N];

int T, n, A, B, idx;
double t, newx, newy, f[N][N];

double dis2(double a1, double b1, double a2, double b2) { return (a1 - a2) * (a1 - a2) * 1.0 + (b1 - b2) * (b1 - b2) * 1.0; }

double dis(double a1, double b1, double a2, double b2) { return (double)sqrt((a1 - a2) * (a1 - a2) * 1.0 + (b1 - b2) * (b1 - b2) * 1.0); }

void work(int xx) {
	int ap, bp, cp;
	for(int i = 0; i <= 2; i++) {
		for(int j = 0; j <= 2; j++) {
			for(int l = 0; l <= 2; l++) {
				if(i == j || j == l || i == l) continue;
				double ka = dis2(a[xx].x[i], a[xx].y[i], a[xx].x[j], a[xx].y[j]);
				double kb = dis2(a[xx].x[j], a[xx].y[j], a[xx].x[l], a[xx].y[l]);
				double kc = dis2(a[xx].x[i], a[xx].y[i], a[xx].x[l], a[xx].y[l]);
				if(ka + kb == kc) ap = l, bp = i, cp = j;
				else continue;
			} 
		}
	}
	double midx = (a[xx].x[ap] + a[xx].x[bp]) / 2.0, midy = (a[xx].y[ap] + a[xx].y[bp]) / 2.0;
	midx *= 2, midy *= 2;
	newx = midx - a[xx].x[cp], newy = midy - a[xx].y[cp];
	return;
}

void init() {
	for(int i = 1; i <= idx; i++) {
		for(int j = 1; j <= idx; j++) {
			if(b[i].id == b[j].id) f[i][j] = f[j][i] = dis(b[i].x, b[i].y, b[j].x, b[j].y) * a[b[i].id].t;
			else f[i][j] = f[j][i] = dis(b[i].x, b[i].y, b[j].x, b[j].y) * t;
		}
	}
	return;
}

void Floyd() {
	for(int k = 1; k <= idx; k++)
	    for(int i = 1; i <= idx; i++)
	        for(int j = 1; j <= idx; j++)
	            if(f[i][j] > f[i][k] + f[k][j]) f[i][j] = f[i][k] + f[k][j];
	return;
}

void print() {
	double res = 1000000000.0;
	for(int i = 1; i <= idx; i++)
		for(int j = 1; j <= idx; j++)
			if(b[i].id == A && b[j].id == B)
				if(res > f[i][j]) res = f[i][j];
	printf("%.1lf\n", res);
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
    cin >> T;
    while(T--) {
    	cin >> n >> t >> A >> B;
    	idx = 0;
    	for(int i = 1; i <= n; i++) {
    		cin >> a[i].x[0] >> a[i].y[0] >> a[i].x[1] >> a[i].y[1] >> a[i].x[2] >> a[i].y[2] >> a[i].t;
    		newx = newy = 0;
    		work(i);
    		a[i].x[3] = newx, a[i].y[3] = newy; 
    		for(int j = 0; j <= 3; j++) b[++idx].id = i, b[idx].x = a[i].x[j], b[idx].y = a[i].y[j];
		}
		init(), Floyd(), print();
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...