题解 P4502【[ZJOI2018] 保镖】

· · 题解

保镖

\color{maroon}{\textsf{Very Hard}}

给大小为 n 的点集 P 和一个矩形区域 R。在矩形区域内均匀随机选择点 O，将 P 中所有点以 O 为中心进行半径为 1 的反演变换。

记变换后点集为 P^\prime，其严格凸包顶点数为 C，求出 \mathbb{E}[C]。

3\leq n\leq 2000.

根据平面图的性质，将数凸包大小 C 转化成数三角剖分的个数T，它们的关系为：C=2n-2-T。指定三角剖分为 Delaunay Triangulation，接下来只讨论 T 的变化。

Delaunay Triangulation 中的每个三角形都满足空圆性：三角形外接圆内没有其他点。称这种圆为内圆，反之若外接圆内包含所有点则为外圆。

对于任意一个内圆，若反演中心在该圆内，反演后该内圆会变成外圆，其他不包含该点的内圆还是内圆。反之，若在某个外圆内，反演后该点变成内圆，其他不包含该点的外圆还是外圆。

数三角剖分个数就是数内圆的个数，根据期望的线性性，每个内外圆对答案的贡献可以单独计算：都是形如一个圆与矩形 R 的交，算出交区域的面积即可。

如何求内圆与外圆？将点 (x,y) 投影到抛物面 z=x^2+y^2 上，即变换为 (x,y,x^2+y^2)。任意平面切该抛物面在 xOy 平面上的投影都是一个圆。因此点集的下凸壳中的每个面都对应一个内圆（所有点都在平面上可以推出没有点在投影的圆内），同理上凸壳的每个面对应一个外圆。

因此只需要求一个三维凸包，需要特殊处理一些点共竖直面的情况，由于 z=x^2+y^2 这个平面本身就是凸的，因此共竖面的点的轮廓自然是个凸包。如果你的三维凸包板子比较鲁棒的话，是能够输出这个凸面的一个三角剖分的。该三角剖分的每个三角对应一个外圆，但是该外圆会退化成一个半平面，因此求出半平面与矩形的交即可。

时间复杂度 \mathcal{O}(n\log n)。

提交记录