半平面交的相关概念

半平面交： 在平面中存在若干条有向直线，每条直线都相当于是对平面的一个划分，对于每条直线，我们只保留它正方向的左半部分，则所有直线保留的部分的交集就称为半平面交。

如果画图观察就可以发现半平面交一定是一个凸多边形。

对于半平面交相关的问题，一般都是要求半平面交的面积，接下来就详细讲解求半平面交面积的算法。

我们这里对于每条有向直线保留左侧部分是人为规定的，也可以保留右侧部分，这里我们的算法中保留是的左侧部分，如果想要求保留右侧部分的半平面交，只需要将所有有向直线反向取反，此时的左侧部分就是原来的右侧部分。

求半平面交的面积：

对于两条方向完全一致的直线，可以发现靠左的直线和靠右的直线的交集刚好就是靠左直线的左侧部分，所以此时靠右直线对于我们求半平面交其实是没有贡献的，因此我们就可以将靠右直线删去，只保留靠左直线即可。通过这样操作最终剩下的所有直线方向一定都是不同的。

我们先将所有直线按照角度从小到大排序，这里对于一个向量 $(x,y)$ 的角度，我们可以用 $atan2(y,x)$ 来求，这是 $\arctan$ 函数的一个封装，可以将所有角度都映射到 $-\pi \sim \pi$ 之间，因此我们可以直接用这个函数来进行排序。这里可以将一个直线的角度看作是逆时针方向上的角度。

然后我们从前往后枚举每条直线，用一个双端队列来维护当前的半平面交中的所有边。我们保证双端队列中至少存在两条边，最开始前两条边直接加入双端队列。对于当前直线，由于不存在相同角度的直线，因此当前枚举的直线一定比队列中所有直线角度更大，然后我们找出队头的两条直线的交点 $p$，如果 $p$ 在当前直线的左侧，则当前直线直接加入队列中，如果 $p$ 在当前直线的右侧，则需要将队头直线删掉，然后在观察当前直线和队头两条直线的交点之间的关系，直到 $p$ 在当前直线的左侧，我们就可以将当前直线加入队列。这一步可以通过画图来理解。

这里除了要维护双端队列的队头，还需要维护双端队列的队尾，我们找出队尾的两条直线的交点 $u$，此时如果当前直线的角度过大，导致 $u$ 在当前直线的右侧，那么我们就需要将队尾直线删掉，然后继续观察当前直线和队尾两条直线的交点之间的关系，直到 $u$ 在当前直线的左侧，就不需要再删除队尾了。这一步也可以通过画图来理解。

由于最终求出来的半平面交是一个凸多边形，所有边是一个环形结构，因此最后我们还要保证双端队列的头和尾之间的联系是合法的，所以我们还需要用队头更新以下队尾，用队尾更新一下队头，保证头尾交接处也是正确的。

注意，前面我们只考虑了交点在直线的右侧是，需要删掉队头或队尾的直线，如果交点在直线上，那么我们需不需要删掉呢，这里需要根据题目来决定，如果题目中要求的是有多少直线和半平面交有交集，那么所有穿过点的直线都要留下来，此时我们如果点在直线上我们就不需要删掉队头或队尾直线。如果只是单纯求面积，那么点在直线上时我们也将队头或队尾直线删掉即可。

这里我们在枚举每条直线的过程中需要去判断点在直线的哪一侧，为了判断方便，我们这里用点向式存储所有直线。

以上算法的时间瓶颈是排序，因此整个的时间复杂度就是 $O(nlogn)$

求半平面交涉及到很多计算几何的常用操作，可以参考 计算几何的基础知识