网站开发整套资料,公司网站设计,外包员工,湖南做网站 x磐石网络正题
题目链接:https://www.luogu.com.cn/problem/P4196 题目大意
给出nnn个凸多边形#xff0c;求它们交的面积。 解题思路
就是把凸多边形上每条边作为一个半平面限制然后求一遍半平面交就好了。
具体做法是我们先将点按照级角排序#xff0c;然后以此把半平面加入双端…正题
题目链接:https://www.luogu.com.cn/problem/P4196 题目大意
给出nnn个凸多边形求它们交的面积。 解题思路
就是把凸多边形上每条边作为一个半平面限制然后求一遍半平面交就好了。
具体做法是我们先将点按照级角排序然后以此把半平面加入双端队列。
加入之前我们需要进行以下操作
如果双端队列头部两个半平面的交点不在新的半平面内那么删去尾部的半平面如果双端队列底部两个半平面的交点不在新的半平面内那么删去尾部的半平面
加入完所有的半平面后我们需要连接队头和队尾此时有可能产生新的多余平面我们拿头部去除尾部多余拿尾部去除头部多余即可步骤与上面相似。
然后得出的相邻半平面两两之间的交点构成一个凸多边形叉积求面积即可。
时间复杂度O(nlogn)O(n\log n)O(nlogn)(n为平面数量) codecodecode
#includecstdio
#includecstring
#includealgorithm
#includecmath
using namespace std;
const int N510;
const double eps1e-8;
int n,m,cnt;double ans;
struct point{double x,y;point(double xx0,double yy0){xxx;yyy;return;}
}p[N];
struct line{point x,y;double dir;line(point xx0,point yy0){xxx;yyy;return;}
}a[N],q[N];
int sign(double x)
{return (xeps)-(x-eps);}
point operator(point x,point y)
{return point(x.xy.x,x.yy.y);}
point operator-(point x,point y)
{return point(x.x-y.x,x.y-y.y);}
point operator(point x,double k)
{return point(x.x*k,x.y*k);}
double operator^(point x,point y)
{return x.x*y.y-x.y*y.x;}
point inter(line x,line y){point s1x.x,s2y.x,t1x.y-s1,t2y.y-s2;return s2(t2(((s2-s1)^t1)/(t1^t2)));
}
bool cmp(line x,line y)
{return sign(x.dir-y.dir)?(sign(x.dir-y.dir)0):(sign((x.y-x.x)^(y.y-x.x))0);}
bool check(line x,line y,line z){point winter(x,y);return sign((z.y-z.x)^(w-z.x))0;
}
void solve(){sort(a1,a1cnt,cmp);n0;for(int i1;icnt;i)if(sign(a[i].dir-a[i-1].dir)!0)a[n]a[i];// for(int i1;in;i)// printf(%lf %lf %lf %lf %d\n,a[i].x.x,a[i].x.y,a[i].y.x,a[i].y.y,i);int tail0,head1;q[1]a[1];q[tail2]a[2];for(int i3;in;i){while(headtailcheck(q[tail-1],q[tail],a[i]))tail--;while(headtailcheck(q[head],q[head1],a[i]))head;q[tail]a[i];}while(headtailcheck(q[tail-1],q[tail],q[head]))tail--;while(headtailcheck(q[head],q[head1],q[tail]))head;n0;q[tail]q[head];for(int ihead1;itail;i)p[n]inter(q[i-1],q[i]);return;
}
int main()
{scanf(%d,n);for(int i1;in;i){scanf(%d,m);point x,last,star;for(int i1;im;i){scanf(%lf%lf,x.x,x.y);if(i1)starx;else a[cnt]line(last,x);lastx;}a[cnt]line(x,star);}for(int i1;icnt;i)a[i].diratan2(a[i].y.y-a[i].x.y,a[i].y.x-a[i].x.x);solve();p[n]p[1];for(int i2;in;i)ans(p[i]^p[i-1]);printf(%.3lf\n,fabs(ans)/2.0);
}
