Lvat_s Blog

裸的半平面交

注意特判一下就好了

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
 
const int N=50005;
const double eps=1e-17;
 
int n,Pn[15],cnt,first,last;
 
struct Point{
double x,y;
Point(){}
Point(double sa,double sb){x=sa;y=sb;}
friend Point operator+(Point A,Point B){return Point(A.x+B.x,A.y+B.y);}
friend Point operator-(Point A,Point B){return Point(A.x-B.x,A.y-B.y);}
friend Point operator*(Point A,double B){return Point(A.x*B,A.y*B);}
friend double operator*(Point A,Point B){return A.x*B.y-A.y*B.x;}
}poi[15][55],Px[N];
 
struct Line{
Point p,v;
double ang;
Line(){}
Line(Point A,Point B){p=A;v=B-A;ang=atan2(v.y,v.x);}
friend bool operator<(Line A,Line B){return A.ang<B.ang;}
}line[N],*Q[N];
 
double Dist2(Point A,Point B){return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);}
Point GetPoint(Line A,Line B){return A.p+A.v*((B.v*(A.p-B.p))/(A.v*B.v));}
bool OnLeft(Point A,Line B){return (A-B.p)*B.v-eps<=0;}
 
void Intersection(){
first=last=0;
sort(line+1,line+cnt+1);
for(int i=1;i<=cnt;i++){
    while(last-first>=2 && !OnLeft(GetPoint(*Q[last],*Q[last-1]),line[i]))Q[last--]=NULL;
    if(last-first>=1 && fabs(Q[last]->v*line[i].v)<=eps)Q[last]=OnLeft(line[i].p,*Q[last])?line+i:Q[last];
    else Q[++last]=line+i;
}
while(last-first>=2 && !OnLeft(GetPoint(*Q[first+1],*Q[first+2]),*Q[last]))Q[++first]=NULL;
while(last-first>=2 && !OnLeft(GetPoint(*Q[last],*Q[last-1]),*Q[first+1]))Q[last--]=NULL;
}
 
double Area(){
//printf("%d %d\n",first,last);
if(last-first<=1)return 0.0;
Q[last+1]=Q[first+1];
cnt=0;
for(int i=first+1;i<=last;i++){
    Px[++cnt]=GetPoint(*Q[i],*Q[i+1]);
    //printf("%.2lf %.2lf\n",Px[cnt].x,Px[cnt].y);
}
Px[cnt+1]=Px[1];
double Ans=0.0;
for(int i=1;i<=cnt;i++){
    Ans+=Px[i]*Px[i+1];
}
return Ans/2.0;
}
 
int main(){
freopen("2618.in","r",stdin);
freopen("2618.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
    scanf("%d",&Pn[i]);
    for(int j=1;j<=Pn[i];j++)scanf("%lf %lf",&poi[i][j].x,&poi[i][j].y);
    poi[i][Pn[i]+1]=poi[i][1];
    for(int j=1;j<=Pn[i];j++)line[++cnt]=Line(poi[i][j],poi[i][j+1]);
}
Intersection();
printf("%.3lf\n",Area());
return 0;
}