题解：CF799G Cut the pie

wjwWeiwei · 2025-04-24 20:33:38 · 题解

怎么又是这种偏 implementation 的计算几何。

考虑定义一个函数 f(\alpha) 代表，经过给定询问点 P 且倾斜角为 \alpha 的直线将凸包划分成的的左半部分与右半部分的面积差。

显然可以发现 f(0)=-f(\pi)，所以我们可以二分找到零点（根据若 x<y,f(x)f(y)\le 0，则 [x,y] 中存在零点）。

现在我们只需要对于一个 \alpha 快速求出 f(\alpha)。这个可以通过找出直线与凸包的两个交点得到，也可以通过二分解决。得到交点后预处理出凸包的前缀叉积和就可以得到两部分的面积。

现在就口胡完了，不过如果你像我一开始写的对上下凸壳分讨交点，就会发现这个实现相当麻烦（也有可能是我太菜了）。

以下内容借鉴自 wxh 大佬的代码。

令 P=(x,y),Q=(x+\cos(\alpha),y+\sin(\alpha))，对于这条倾斜角为 \alpha 的直线，我们在其上取向量 (P,Q)。

当初始点 a_{st} 在向量左侧时：

若当前二分点 a_{mid} 在向量右侧，可以通过向前或向后找来寻找两个交点。

若 a_{mid} 在向量左侧，可以根据叉积判断 a_{mid} 是否在向量 (a_{st},P)右侧。如果是的话则 l\leftarrow mid+1，否则 r\leftarrow mid-1。