自动搬运

查看原文

来自洛谷，原作者为

	FangZeLi 宁愿重伤也不愿悲伤，让伤痕变成了我的徽章，刺在我心脏，永远不忘。

搬运于2025-08-24 22:25:01，当前版本为作者最后更新于2021-04-24 16:33:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Link

[ICPC2014 WF]Messenger

Solution

咳咳咳，为啥ICPC这么喜欢几何题

言归正传，我们分析下这道题目。

显然这题的计算几何部分不是重点，那么我们主要分析这个运动过程。

题目中是两个人同时在运动，然后随便分析一下，我们就可以看出：由于两个人都是匀速直线运动，那么我们直接将一个人选作参考系，就可以转化为只有一个人运动。

那么现在问题已经弱化很多了，可是还是不是非常好处理。

一个关键的想法：这个送邮递的过程，可以这样转化一下。我们不妨直接把邮递员这个工具人直接删了，把这个过程转换为Nadia提前了$t$出发，那么，在这种情况下，只要Misha（现在一直在原点）到Nadia路径的任何一段距离小于$t$，那么$t$的送货时间就是可行的。

然后就是一些细节问题。由于每次涉及到提前一个人，所以每次的相对路径需要重新计算。然后由于是浮点数，需要注意一下精度问题。~~但凡涉及到浮点数的题目我必定要交两三面。~~最终复杂度 $\mathcal{O}(n\log n)$。

Code

#include <cstdio>
#include <cmath>

#define _N 50010
#define _EPS 1e-8

struct Tuple {
	double x, y;
	Tuple() {
		x = y = 0;
	}
	Tuple(double a, double b) {
		x = a, y = b;
	}
};

Tuple inline operator +(const Tuple& left, const Tuple& right) {
	return Tuple(left.x + right.x, left.y + right.y);
}
Tuple inline operator -(const Tuple& left, const Tuple right) {
	return Tuple(left.x - right.x, left.y - right.y);
}
Tuple inline operator *(const Tuple& left, double right) {
	return Tuple(left.x * right, left.y * right);
}
double inline operator *(const Tuple& left, const Tuple& right) {
	return left.x * right.x + left.y * right.y;
}
Tuple inline operator /(const Tuple& left, double right) {
	return Tuple(left.x / right, left.y / right);
}
double inline operator %(const Tuple& left, const Tuple& right) {
	return left.x * right.y - left.y * right.x;
}

typedef Tuple Point;
typedef Tuple Vec;

int n, m;

Point misha[_N];
Point nadia[_N];
double disn[_N];

int inline sgn(double val) {
	if (val > _EPS) {
		return 1;
	}
	if (val < -_EPS) {
		return -1;
	}
	return 0;
}

double inline dist(Point left, Point right) {
	return sqrtl((right.x - left.x) * (right.x - left.x) + (right.y - left.y) * (right.y - left.y));
}
double inline len(Vec val) {
	return sqrtl(val.x * val.x + val.y * val.y);
}
double inline dist(Point p, Point left, Point right) {
	double len = dist(left, right);
	if (len > _EPS && sgn((p - left) * (right - left)) >= 0 && sgn((p - right) * (left - right)) >= 0) {
		return fabsl((p - left) % (right - left)) / len;
	}
	return fminl(dist(p, left), dist(p, right));
}
Point inline at(Point from, Point to, double len) {
	return from + (to - from) * len / dist(from, to);
}
Vec inline unit(Vec val) {
	return val / len(val);
}

bool check(double delay) {
	int ptm = 1, ptn = 1;
	double remm = 0, remn = delay;
	Point lastm = misha[1], lastn;
	while (ptn < m && disn[ptn] < delay + _EPS) {
		ptn++;
	}
	if (ptn == m) {
		return true;
	}
	remn -= disn[ptn - 1];
	lastn = at(nadia[ptn], nadia[ptn + 1], remn);
	while (ptm < n && ptn < m) {
		if (dist(lastm, lastn) < delay + _EPS) {
			return true;
		}
		double timm = dist(lastm, misha[ptm + 1]), timn = dist(lastn, nadia[ptn + 1]);
		Vec relamov = (unit(nadia[ptn + 1] - lastn) - unit(misha[ptm + 1] - lastm)) * fminl(timm, timn);
		if (timm > _EPS && timn > _EPS && dist(lastm, lastn, lastn + relamov) < delay + _EPS) {
			return true;
		}
		int cmp = sgn(timm - timn);
		if (cmp == 1) {
			remm += timn, remn = 0;
			lastm = at(misha[ptm], misha[ptm + 1], remm), lastn = nadia[++ptn];
		} else if (cmp == -1) {
			remn += timm, remm = 0;
			lastn = at(nadia[ptn], nadia[ptn + 1], remn), lastm = misha[++ptm];
		} else {
			remm = remn = 0;
			lastm = misha[++ptm], lastn = nadia[++ptn];
		}
	}
	return false;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lf%lf", &misha[i].x, &misha[i].y);
	}
	scanf("%d", &m);
	for (int i = 1; i <= m; i++) {
		scanf("%lf%lf", &nadia[i].x, &nadia[i].y);
	}
	for (int i = 1; i < m; i++) {
		disn[i] = dist(nadia[i], nadia[i + 1]);
		disn[i] += disn[i - 1];
	}
	double l = 0, r = disn[m - 1];
	if (dist(misha[1], nadia[m]) > r + _EPS) {
		puts("impossible");
		return 0;
	}
	while (r - l > _EPS) {
		double mid = (l + r) / 2;
		if (check(mid)) {
			r = mid;
		} else {
			l = mid;
		}
	}
	printf("%.4lf\n", (l + r) / 2);
	return 0;
}

Inspiration

我认为这题的转化如果是第一次接触还是有点难度的，不过其他的部分都不难。

关键结论：

• 两个匀速直线运动可以通过变换参考系变成静止和一个匀速直线运动。
• 邮递员可以通过转化简单的考虑