题解：CF799G Cut the pie

怎么又是这种偏 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$。

$a_{st}$ 在向量右侧同理。

这样我们就做完了，卡卡精度就能过了。

怎么主播喜欢写粪啊（