凸多边形

这道题代码很短，但是66行的代码笔者调了近4个小时

推荐理由

这个题十分的考细节，稍微不注意就凉凉
写完这道题也可以对计算几何有更深入的理解（虽然是模板题QWQ）

前置知识

• 平面向量： https://baike.baidu.com/item/%E5%B9%B3%E9%9D%A2%E5%90%91%E9%87%8F/448934?fr=aladdin
• 向量的叉积： https://baike.baidu.com/item/%E5%90%91%E9%87%8F%E7%A7%AF/4601007?fr=aladdin
• 利用向量的叉集计算多边形面积： 自己百度
• 向量表示的直线求交点（我们一般使用“两点式”来表示一条直线）

思路

题面要求求n个多边形的交集的面积
我们考虑把每个多边形拆成一条一条边
题面转为半平面交问题

实现

我觉得这个博客写的很好，我就不重复造轮子了QWQ
https://blog.csdn.net/qq_40861916/article/details/83541403
笔者在调试代码时还出现了浮点数输出nan的问题
为了避免大家绕圈子，可以参考： https://baike.baidu.com/item/nan/7455322?fr=aladdin
特判一下即可

参考代码

#include<bits/stdc++.h>
using namespace std;
struct point{
    double x,y;
    point(){};
    point(double x,double y):x(x),y(y){};
    point operator-(point b){return point(x-b.x,y-b.y);}
    point operator+(point b){return point(x+b.x,y+b.y);}
    point operator*(double b){return point(x*b,y*b);}
    double operator%(point b){return x*b.y-y*b.x;}
}d[1010];
struct line{
    point st,ed;
    double get_slope(){return atan2((ed-st).y,(ed-st).x);}
    bool operator<(line b){
        double a=this->get_slope();
        double c=b.get_slope();
        if(fabs(a-c)>1e-8)
            return a<c;
        return (b.st-st)%(b.ed-st)>0;
    }
}p[1010];
point get_intersection(line s,line t){
    double k=((t.ed-t.st)%(s.st-t.st))/((s.ed-s.st)%(t.ed-t.st));
    return s.st+(s.ed-s.st)*k;
}
bool is_right(point a,line b){
    return (a-b.st)%(b.ed-b.st)>=0;
}
int cnt,n,stk[1010],hh=-1,tt;
double work(){
    sort(p+1,p+n+1);
    for(int i=1;i<=n;i++){
        if(i!=1&&fabs(p[i].get_slope()-p[i-1].get_slope())<1e-8) continue;
        while(tt+1<=hh && is_right(get_intersection(p[stk[hh]],p[stk[hh-1]]),p[i])) hh--;
        while(tt+1<=hh && is_right(get_intersection(p[stk[tt]],p[stk[tt+1]]),p[i])) tt++;
        stk[++hh]=i;
    }
    while(tt+1<=hh && is_right(get_intersection(p[stk[hh]],p[stk[hh-1]]),p[stk[tt]])) hh--;
    while(tt+1<=hh && is_right(get_intersection(p[stk[tt]],p[stk[tt+1]]),p[stk[hh]])) tt++;
    stk[++hh]=stk[tt];
    int k=0;
    for(int i=tt;i<hh;i++)
        d[++k] = get_intersection(p[stk[i]],p[stk[i+1]]);
    double res=0;
    for(int i=1;i<=k;i++)
        res+=d[i]%d[i%k+1];
    return fabs(res/2);
}
int main(){
    cin>>cnt;
    for(int i=1;i<=cnt;i++){
        int m;
        scanf("%d",&m);
        for(int j=0;j<m;j++)
            scanf("%lf%lf",&d[j].x,&d[j].y);
        for(int j=0;j<m;j++){
            p[++n].st=d[j];
            p[n].ed=d[(j+1)%m];
        }
    }
    double ans=work();
    ans= ans==ans?ans:0;
    printf("%.3lf",ans);
    return 0;
}