基础定义​

//圆周率
#define Pi acos(-1)

//结构体-点
struct Point{double x, y;};

//结构体-线
struct line{double a, b, c;};

//逆时针旋转向量（弧度）
Point Rotate(Point a, double rad)
{return (Point){a.x*cos(rad)-a.y*sin(rad), a.x*sin(rad)+a.y*cos(rad)};}

//叉积，a*b>0表示向量b在向量a的左边
double operator * (Point a, Point b){return a.x*b.y-a.y*b.x;}

//向量求极角
atan2(b.y-a.y, b.x-a.x)

半平面交

sort(l+1, l+m+1); //极角排序
cnt=0; 
rep(i, 1, m)
{
    if (l[i].ang!=a[cnt].ang) cnt++;
    a[cnt]=l[i];
} //极角排重
L=1, R=0; q[++R]=a[1]; q[++R]=a[2];
rep(i, 3, cnt)
{
    while (L<R && jud(q[R-1], q[R], a[i])) R--;
    while (L<R && jud(a[i], q[L], q[L+1])) L++;
    q[++R]=a[i];
}
while (L<R && jud(q[R-1], q[R], q[L])) R--;
while (L<R && jud(q[R], q[L], q[L+1])) L++;

凸包

int k=1;
rep(i, 2, n) if (p[i].y<p[k].y || (p[i].y==p[k].y && p[i].x<p[k].x)) k=i;
swap(p[1], p[k]); 
//先把横纵坐标最小的点移至第一
sort(p+2, p+n+1, cmp); 
//所有点顺时针排列，相同角度时按距离从小到大排
s[++top]=p[1]; s[++top]=p[2];
rep(i, 3, n)
{
    while (top>1 && (p[i]-s[top-1])*(s[top]-s[top-1])<=0) top--;
    s[++top]=p[i];
}

动态加点维护凸包

//点按照横纵坐标排序
set<P>::iterator r=q.lower_bound(p), l=r, t; l--;
if ((*r-*l)*(p-*l)<0) return;
now-=dis(*l, *r);
while (1)
{
    t=r++;
    if (r==q.end()) break;
    if ((*r-p)*(*t-p)>0) break;
    now-=dis(*t, *r);
    q.erase(t);
}
while (l!=q.begin())
{
    t=l--;
    if ((*t-p)*(*l-p)>0) break;
    now-=dis(*t, *l);
    q.erase(t);
}
q.insert(p); l=r=q.find(p); l--; r++;

圆

圆心角$\theta$所对弓形面积：$S=\frac{1}{2}r^2(\theta - sin(\theta))$（部分圆减去三角形部分）

圆交

四种情况：相离相切、相交且两圆心分居公共弦两侧、相交且两圆心位于公共弦一侧、包含

半平面交

Step1：将所有半平面按极角排序，对于极角相同的，选择性的保留一个

Step2：使用一个双端队列，加入最开始2个半平面

Step3：每次考虑一个新的半平面：

a.假如队列顶端的两个半平面的交点在当前半平面外，删除deque顶端的半平面

b.假如队列底部的两个半平面的交点在当前半平面外，删除deque底部的半平面

c.将新半平面加入队列顶端

Step4：删除两端多余的半平面：

a.假如队列顶端的两个半平面的交点在底部半平面外，删除deque顶端的半平面

b.假如队列底部的两个半平面的交点在顶端半平面外，删除deque底部的半平面

Step5：计算出deque顶端和底部的交点即可

#define eps 1e-8

int n, x[maxn], y[maxn];
struct node{int x1,y1,x2,y2; ld a;} k[maxn], q[maxn], g[maxn]; int L, R, tot; bool fg;
struct P{ld x,y;} p[maxn];

inline bool Right(node a, P b){return (b.y-a.y1)*(a.x2-a.x1)-(b.x-a.x1)*(a.y2-a.y1)<0;}

inline P cross(node a, node b)
{
	ld a1=a.y2-a.y1, b1=a.x1-a.x2, c1=1LL*a.x2*a.y1-1LL*a.x1*a.y2;
	ld a2=b.y2-b.y1, b2=b.x1-b.x2, c2=1LL*b.x2*b.y1-1LL*b.x1*b.y2;
	if (fabs(fabs(a.a-b.a)-atan2(0,-1))<eps) fg=true; // fg为true时答案为空集
	return (P){(b1*c2-b2*c1)/(a1*b2-a2*b1),(a1*c2-a2*c1)/(b1*a2-b2*a1)};
}

bool cmp(node a, node b) {return a.a>b.a;}

int main()
{
	
	//........
	
	rep(i, 1, n) k[i]=(node){x[i],y[i],x[i+1],y[i+1],atan2(y[i+1]-y[i],x[i+1]-x[i])};
	sort(k+1, k+1+n, cmp);
	
	g[tot=1]=k[1]; rep(i, 2, n) 
		if (k[i-1].a-k[i].a>eps) g[++tot]=k[i];
		else if (Right(g[tot],(P){(ld)k[i].x1,(ld)k[i].y1})) g[tot]=k[i];
		
	L=1, R=0, q[++R]=g[1], q[++R]=g[2];
	rep(i, 3, tot)
	{
		while (L<R && !Right(g[i],cross(q[R],q[R-1]))) R--;
		while (L<R && !Right(g[i],cross(q[L],q[L+1]))) L++;
		q[++R]=g[i];
	}
	while (L<R && !Right(q[L],cross(q[R],q[R-1]))) R--;
	while (L<R && !Right(q[R],cross(q[L],q[L+1]))) L++;
	
	//........
	
	return 0;
}