半平面交

统一

半平面交:一条直线/向量将二维平面分成两部分,其中一部分就是半平面,现在求多条直线/向量给定半平面的交集。

这里,我们统一使用向量,并且假设一个向量的左边平面为给定半平面(如果一个向量的给定平面在其右边,那我们就把这个向量反向即可)。

判断

如何判断一个点(C)是否在一个向量(overrightarrow {AB})右边?在向量上任意找一点 (A) ,满足 (overrightarrow {AB} imes overrightarrow {AC}gt 0)

半平面交

我们先把向量极角排序(也可以先对给定直线通过斜率排序)。然后把相同极角向量(斜率相同)的进行一次贪心选取,因为我们假定是左边平面,那么相同极角的(vec a)(vec b),如果(vec a)(vec b)左边,那么贪心选取(vec a)(b)直接不可能贡献答案直接丢掉。如何判断是否在左边?直接在(vec b)上取任意一点判断是否在(vec a)右边即可。

接下来我们需要依次往单调队列里面按排好序的顺序添加边。添加之前需要判断前两条边的交点是否在添加边的右边,若是,删除最后一条边,同时也这样处理一下队首。

最后做完后,我们保证通过最后一条边限制了前面的边,但是添加过程中并未考虑添加边是否多余,于是判断队尾两边的交点是否在队首右边,如果在就删除队尾的边。

半平面交弱化版例题:

P3194

此题不需要弹出队首,也不需要在最后检查队尾,因为向量方向可以直接认为是向正方向的,最后交集是开放的,不可能成环。

原文地址:https://www.cnblogs.com/redegg/p/11979993.html