题解：AT_agc021_b [AGC021B] Holes

dingziyang888 · 2026-07-19 10:16:09 · 题解

首先题目里这个 R 非常大，我们可以直接看成无限大的平面。

然后如果一个点集构成了一个有限的平面，那么在这个无限大的平面中他们取到的概率就是 0，而剩下的点构成一个凸包，这里面的点显然答案是非 0 的。

那么对于凸包上的一个顶点 B，他能让这个人掉进去的区域容易想到就是相邻两个凸包顶点 A 和 C 连线的中垂线围成的一个无限的楔形区域，角度为 \pi-\angle ABC，因此点 B 对应的概率就是 \dfrac{\pi-\angle ABC}{2\pi}。

用 Andrew 法求凸包即可。。。

Submission。