题解 P4250 【[SCOI2015]小凸想跑步】

推波柿子：  设点$A(x_a, y_a), B(x_b, y_b), C(x_c, y_c), D(x_d, y_d), P(x, y)$ $\vec{a} = (x_b - x_a, y_b - y_a), \vec{b} = (x_d - x_c, y_d - y_c)$ $\overrightarrow{AP} = (x - x_a, y - y_a), \overrightarrow{CP} = (x - x_c, y - y_c)$ $\vec{a} \times \overrightarrow{AP} = (x_b - x_a)(y - y_a) - (y_b - y_a)(x - x_a)$ $\vec{b} \times \overrightarrow{CP} = (x_d - x_c)(y - y_c) - (y_d - y_c)(x - x_c)$ 由题目，$\vec{a} \times \overrightarrow{AP} < \vec{b} \times \overrightarrow{CP}$，那么有 $$\begin{aligned}&(x_b - x_a)(y - y_a) - (y_b - y_a)(x - x_a) < (x_d - x_c)(y - y_c) - (y_d - y_c)(x - x_c) \\\Rightarrow & (x_b - x_a + x_d - x_c)y - (y_b - y_a - y_d + y_c)x + (y_b x_a - x_b y_a - y_d x_c + x_d y_c) < 0\end{aligned}$$ 然后这个就是一个裸的半平面交了。 代码见[$\texttt{my blog}$](https://www.cnblogs.com/cj-xxz/p/10603286.html)