Warning: session_start(): open(/tmp/sess_3ea1bef070dcda4f7bce928262c7fc21, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/4/43994124a9168f34c03db2ff7cd35d94.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== 半平面交 ======
给定n个形如 $ax+by+c\le0$ 的半平面，找到所有满足它们的点所组成的额点集，称为半平面交。
相交后的区域可能是直线、射线、线段或者点，甚至也有可能是空集。
===== 求解算法 排序增量法 =====
把半平面分成两部分，一部分是极角范围内的 $(-\frac{\pi}{2},\frac{\pi}{2})$ ，另一部分是极角范围外的角度。
考虑 $(-\frac{\pi}{2},\frac{\pi}{2})$ 的半平面，将他们按照极角排序。极角相同的半平面根据常数项保留一个。
然后从排序后极角最小的两个半平面开始，求出他们的交点并将它们压入一个栈，每次按照极角从小到大的顺序增加一个半平面，算出他和栈顶半平面的交点。如果当前的交点在栈顶两个半平面交点的右边，则让它出栈。
===== 例题 =====
[[https://www.luogu.com.cn/problem/P4196|洛谷]]
大致题意
求 $n$ 个多边形的交
把每个多边形表示成半平面交的形式，然后只需计算所有的半平面交。
代码
#include
using namespace std;
const double eps=1e-13;
struct point
{
double x,y;
point operator -(point &s)
{
return (point){x-s.x,y-s.y};
}
};
double operator *(point a,point b)
{
return a.x*b.y-a.y*b.x;
}
struct line
{
double d;
point a,b;
}l[1005];
bool cmpd(line a,line b)
{
return a.d>n;
for (int i=1;i<=n;i++)
{
int mm;
cin>>mm;
for (int j=1;j<=mm;j++)
{
m++,cin>>l[m].a.x>>l[m].a.y;
l[(j==1)?m+mm-1:m-1].b=l[m].a;
}
}
n=m;
for (int i=1;i<=n;i++)
l[i].d=atan2(l[i].b.y-l[i].a.y,l[i].b.x-l[i].a.x);
sort(&l[1],&l[n+1],cmpd);
for (int i=1;i<=n;i++)
{
for (;sta[0]>=1;sta[0]--)
{
if (fabs(l[i].d-l[sta[sta[0]]].d)=2;sta[0]--)
{
if ((l[i].b-l[i].a)*(crosp(l[sta[sta[0]]],l[sta[sta[0]-1]])-l[i].a)>eps) break;
}
if (fabs(l[i].d-l[sta[sta[0]]].d)>=eps) sta[++sta[0]]=i;
}
int L=1,R=sta[0];
while (L