题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=2618
半平面交板子题
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 |
#include<bits/stdc++.h> #define db double #define maxn 505 #define eps 1e-7 #define Vector point using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } struct point{ db x,y; point(db xx=0,db yy=0){x=xx,y=yy;} friend point operator + (Vector a,Vector b){return point(a.x+b.x,a.y+b.y);} friend point operator - (Vector a,Vector b){return point(a.x-b.x,a.y-b.y);} friend point operator * (Vector a,db b){return point(a.x*b,a.y*b);} friend point operator / (Vector a,db b){return point(a.x/b,a.y/b);} friend bool operator < (Vector a,Vector b){return a.x<b.x || fabs(a.x-b.x)<eps && a.y<b.y;} }p[maxn],a[maxn]; struct line{ point p,v; db ang; line(){} line(point P,Vector V){ p=P; v=V; ang=atan2(v.y,v.x); } friend bool operator < (line a,line b){ return a.ang<b.ang; } }L[maxn],q[maxn]; inline db cross(Vector A,Vector B){return A.x*B.y-A.y*B.x;} inline point GetPoint(line a,line b){ Vector V=a.p-b.p; db t=cross(b.v,V)/cross(a.v,b.v); return a.p+a.v*t; } inline bool Onleft(line l,point p){ return cross(l.v,p-l.p)>0; } int cnt; inline void init(){ int T=rd(); while(T--){ int n=rd(); for(int i=1; i<=n; i++)p[i].x=rd(),p[i].y=rd(); p[n+1]=p[1]; for(int i=1; i<=n; i++)L[++cnt]=line(p[i],p[i+1]-p[i]); } } int head=1,tail=0; inline void hpi(){ sort(L+1,L+cnt+1); q[++tail]=L[1]; for(int i=2; i<=cnt; i++){ while(head<tail && !Onleft(L[i],p[tail-1]))tail--; while(head<tail && !Onleft(L[i],p[head]))head++; q[++tail]=L[i]; if(fabs(cross(q[tail].v,q[tail-1].v))<eps){ tail--; if(Onleft(q[tail],L[i].p))q[tail]=L[i]; } if(head<tail)p[tail-1]=GetPoint(q[tail-1],q[tail]); } while(head<tail && !Onleft(q[head],p[tail-1]))tail--; p[tail]=GetPoint(q[tail],q[head]); } inline void work(){ hpi(); db ans=0; for(int i=head+1; i<tail; i++){ ans+=cross(p[i]-p[head],p[i+1]-p[head]); } printf("%.3lf\n",ans*0.5); } int main(){ init(); work(); return 0; } |
《bzoj 2618: [Cqoi2006]凸多边形 半平面交》有1个想法