这道题代码很短,但是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; }