luogu P4196
程序员文章站
2022-06-02 21:26:18
...
题意
给一些多边形,求这些多边形的面积并
数据范围
每个多边形至多50条边,至多有10个多边形
解法
半平面交
这里介绍的是的做法:
首先考虑如何比较优秀的直线求交,这个是接下来算法步骤的灵魂问题
考虑使用面积法:
如图,可以看到三角形p1p2v1和四边形p1p2v1v2同底,所以它们的面积比就是高之比,又由于相似,它们的高之比可以看成线段(p2-交点)和(p2-v2)的长度之比。所以求出这个之后加上p2就可以得到交点的坐标了。
然后考虑半平面交问题,这里我们规定所有线段都是左边为有效区间,然后将所有线段一起按照极角排序,相同极角的靠左边的放在后面,然后用双端队列维护半平面交,计算的时候就是考虑一条线段加进去后,会不会影响之前的半平面交。又了直线求交的方法后就比较简单了,具体可以看代码。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
const double eps=1e-7;
struct node{
double x,y;
node (double xx=0,double yy=0){x=xx,y=yy;}
}b[maxn];
double operator ^(node a,node b){return a.x*b.y-a.y*b.x;}
node operator +(node a,node b){return node(a.x+b.x,a.y+b.y);}
node operator -(node a,node b){return node(a.x-b.x,a.y-b.y);}
node operator *(double a,node b){return node(a*b.x,a*b.y);}
struct line{
node v,p;
double poa;
}a[maxn],q[maxn];
int n,js;
inline int sign(double a){
if(fabs(a)<=eps)return 0;
return a>0?1:-1;
}
bool cmp(line a,line b){
if(sign(a.poa-b.poa))return sign(a.poa-b.poa)<0;
else return sign((a.v-a.p)^(b.v-a.p))>0;
}
node inter(line a,line b){
node p1=a.p,v1=a.v,p2=b.p,v2=b.v;
v1=v1-p1,v2=v2-p2;
node alfa=p2-p1;
node tmp=p2+((alfa^v1)/(v1^v2))*v2;
return tmp;
}
int cnt=0;
inline bool pd(line a,line b,line c){
node p=inter(a,b);
return sign((c.v-c.p)^(p-c.p))<0;
}
void bpm(){
sort(a+1,a+1+js,cmp);
for(int i=1;i<=js;i++){
if(sign(a[i].poa-a[i-1].poa)!=0)cnt++;//极角不同才保留
a[cnt]=a[i];
}
int h=1,t=0;
q[++t]=a[1],q[++t]=a[2];
for(int i=3;i<=cnt;i++){
while(h<t&&pd(q[t-1],q[t],a[i]))t--;
while(h<t&&pd(q[h+1],q[h],a[i]))h++;
q[++t]=a[i];
}
while(h<t&&pd(q[t-1],q[t],q[h]))t--;//注意最后要记得把头和尾判断一下
while(h<t&&pd(q[h+1],q[h],q[t]))h++;
q[t+1]=q[h];//这里容易忘记,因为是多边形,首尾相连
js=0;
for(int i=h;i<=t;i++){
b[++js]=inter(q[i],q[i+1]);
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
int k;
scanf("%d",&k);
for(int j=1;j<=k;j++){
scanf("%lf%lf",&b[j].x,&b[j].y);
}
b[k+1]=b[1];
for(int j=1;j<=k;j++)a[++js].p=b[j],a[js].v=b[j+1];
}
for(int i=1;i<=js;i++)
a[i].poa=atan2(a[i].v.y-a[i].p.y,a[i].v.x-a[i].p.x);
bpm();
b[js+1]=b[1];
double ans=0;
if(js>2)
for(int i=1;i<=js;i++)ans+=b[i]^b[i+1];
ans=fabs(ans)/2.0;
printf("%.3lf\n",ans);
return 0;
}
上一篇: ~关于显示自定义长度字符串的有关问题
下一篇: 双截棍
推荐阅读