【2026ICPC深圳邀请赛】M. 博物馆惊魂夜

题目大意

一名保安在博物馆巡逻以监控展品。巡逻路线是一条由 $n$ 个点（编号从 1 到 $n$）组成的闭合折线，这些点按顺序连接（最后一个点连接回第一个点）形成 $n$ 个连续的线段。保安按照 $1 \rightarrow 2 \rightarrow \cdots \rightarrow n \rightarrow 1 \rightarrow \cdots$ 的顺序进行巡逻。当保安不在线段端点时，其视野是一个半径为 $r$、圆心角为 $2a$ 的扇形，该扇形的角平分线与巡逻线段的前进方向一致。

巡逻线段上的一点 $P$（不包括端点）能够看到位于点 $Q$ 的展品，当且仅当 $Q$ 位于以 $P$ 为顶点的扇形区域内。给定由 $n$ 个点定义的闭合折线巡逻路线和 $m$ 个展品的位置，对于每一个 $k = 0, 1, \dots, m$，求恰好能看到 $k$ 个展品的巡逻路线的总长度。

输入

每个测试文件中仅包含一个测试用例。

第一行包含四个整数 $n$、$m$、$r$ 和 $a$（$3 \le n \le 2 \times 10^3$，$1 \le m \le 2 \times 10^3$，$1 \le r \le 10^4$，$0 < a < 90$），分别表示闭合折线的点数、展品的数量、视野的半径以及视野的半角（单位为度）。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$-10^4 \le x_i, y_i \le 10^4$），表示折线第 $i$ 个点的坐标。连续的点构成巡逻线段，且最后一个点与第一个点相连以形成闭合回路。保证任意两个连续的点（包括最后一个点和第一个点）都不重合。

接下来的 $m$ 行中，第 $i$ 行包含两个整数 $x’_i$ 和 $y’_i$（$-10^4 \le x’_i, y’_i \le 10^4$），表示第 $i$ 个展品的坐标。

输出

输出 $(m + 1)$ 行，其中第 $i$ 行包含一个实数，表示恰好能看到 $(i - 1)$ 个展品的巡逻路线的总长度。

如果你的答案的绝对误差或相对误差不超过 $10^{-6}$，则被视为正确。形式化地说，假设你的答案是 $a$，标准答案是 $b$，当且仅当 $\frac{|a-b|}{\max(1, |b|)} \le 10^{-6}$ 时，你的答案才会被接受。

题解

赛场上刚刚看到这个题的时候，觉得是什么面积并之类的东西，感觉不太可做。后来他们在那里开别的题，我就接着去。比赛还剩 $80$ 分钟的时候开始敲代码，连想带敲花了一个小时，最后测样例发现都没输出。最后 $15$ 分钟调发现左端点大于右端点导致数组越界了，只能遗憾打印代码，赛后补题。补题的时候发现这个题大概思路其实还简单的，就是要注意的细节稍微有点多，要是从赛时两个小时开始做这个题可能就过了，有时间调一下代码。到底什么时候才能在赛时把几何开出来口牙。

总的来说这个题的核心思路就是做一个类似扫描线的东西来判断这一段小区间内被多少区间覆盖了。保安形成的扇形区域向前移动，很容易得到在这个路径上：哪个点使得刚好看见藏品，哪个点刚好看不见藏品。除此以外，可以通过旋转向量的方式来简化实现，这样该线段就直接与 $x$ 轴平行了，我是把他巡逻的方向永远朝向 $x$ 轴负方向。具体实现请看代码吧。

#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
const int N = 2e3 + 50;
const double PI = acos(-1.0);  // 3.1415926...
typedef pair<double, int> pii; // 向量
struct point
{
	double x, y;
};

point operator+(point a, point b) { return point{a.x + b.x, a.y + b.y}; } //+
point operator-(point a, point b) { return point{a.x - b.x, a.y - b.y}; } //-
point operator*(point a, double t) { return point{a.x * t, a.y * t}; }	  // 数乘
point operator*(double t, point a) { return point{a.x * t, a.y * t}; }	  // 数乘
double dot(point a, point b) { return a.x * b.x + a.y * b.y; }			  // 点积
point rotate(point a, double altha)
{
	return point{a.x * cos(altha) - a.y * sin(altha), a.x * sin(altha) + a.y * cos(altha)};
} // 向量的旋转（逆时针旋转）

typedef point Vector; // 向量
double len(Vector a)
{
	return sqrt(dot(a, a));
}
point p[N], q[N], tmp[N];
int n, m, r, a;
double ans[N];
int nxt(int x)
{
	if (x == n)
		return 1;
	else
		return x + 1;
}

void solve()
{
	cin >> n >> m >> r >> a;
	for (int i = 1; i <= n; ++i)
	{
		int x, y;
		cin >> x >> y;
		p[i] = {1.0 * x, 1.0 * y};
	}

	for (int i = 1; i <= m; ++i)
	{
		int x, y;
		cin >> x >> y;
		q[i] = {1.0 * x, 1.0 * y};
	}

	for (int i = 1; i <= n; ++i)
	{
		point p1 = p[i], p2 = p[nxt(i)];
		Vector v = p[nxt(i)] - p[i];
		double ang = -atan2(v.y, v.x) + PI;
		p1 = rotate(p1, ang), p2 = rotate(p2, ang);
		for (int j = 1; j <= m; ++j)
			tmp[j] = rotate(q[j], ang);

		double H = 1.0 * r * sin(1.0 * a / 180 * PI);
		vector<pii> all;
		for (int j = 1; j <= m; ++j)
		{
			auto [x, y] = tmp[j];
			if (fabs(y - p1.y) > H)
				continue;
			double h = fabs(y - p1.y);
			double LL = min(p1.x, p2.x), RR = max(p1.x, p2.x);
			double R = max(LL, min(r * cos(1.0 * asin(1.0 * h / r)) + x, RR));
			double L = max(LL, min(h / tan(1.0 * a / 180 * PI) + x, RR));
			all.push_back({L, 0}), all.push_back({R, 1});
		}

		sort(all.begin(), all.end());
		int now = 0;
		if (!all.size())
			ans[0] += len(p1 - p2);
		else
		{
			ans[0] += all[0].first - min(p1.x, p2.x), ans[0] += max(p1.x, p2.x) - all.back().first;
			for (int j = 0; j < all.size() - 1; ++j)
			{

				if (!all[j].second)
					now++;
				if (all[j].second)
					now--;
				ans[now] += all[j + 1].first - all[j].first;
			}
		}
	}

	for (int i = 0; i <= m; ++i)
		cout << fixed << setprecision(18) << ans[i] << endl;
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int T = 1;
	// cin >> T;

	while (T--)
		solve();
}

题面翻译 by Qwen3.6-Plus