【学习笔记】半平面交转凸包
维护向上的半平面交，即若干形如 $y \geq kx + b$ 的半平面的并，答案形如凸包下凸壳。
说真的没人写过 $> 1$ 次半平面交吧，因为有更好写更清真拓展性更强的对偶问题——凸包啊！它的对偶问题是将直线 $y = kx + b$ 视为点 $(k, b)$ 然后作凸包上凸壳。
证明很容易：
考虑半平面交，已有 $a$、$b$ 两条直线，再加入直线 $c$，能弹走 $b$ 当且仅当 $a$、$b$ 的交点 $(x_0, y_0) = (-\frac{a.b - b.b}{a.k - b.k}, \frac{a.k * b.b - a.b * b.k}{a.k - b.k})$ 在 $c$ 下方，即 $y = c.k * x_0 + c.b > y_0$ ($I$)
考虑凸包，已有 $A$、$B$ 两个点，加入点 $C$，能弹走 $B$ 当且仅当 $(B - A) * (C - A) \geq 0$，即 $(b.k - a.k) * (c.b - a.b) - (b.b - a.b) * (c.k - a.k) \geq 0$ ($II$)
而 $I = II$！证明完毕。
例题
显然是半平面交。
向上的半平面交答案形如下凸包，对偶一下变成求上凸包
判某个点 $(x, y)$ 是否在半平面交内转为切凸包问题
据说可以李树做到 $O(nlog^2n)$
我们考虑 SGT 维护凸包，在 SGT 和凸包上二分是两只 $log$，然而只要对询问按 $x$ 排序就优化掉凸包那只 $log$ 了。$O(nlogn)$。