【模板/经典题型】半平面交

妖狐艹你老母 2021-10-01 03:48 296阅读 0赞

写半平面交的时候注意以下几点  
1.考虑x,y是否有正负号限制。  
2.注意特判分母为0的情况。  
3.对于分母正负不确定的情况分类讨论。

#include<iostream> #include<cctype> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<ctime> #include<cstdlib> #include<algorithm> #define N 1100000 #define L 1000000 #define eps 1e-7 #define inf 1e9+7 #define db double #define ll long long #define ldb long double using namespace std; inline int read() { char ch=0; int x=0,flag=1; while(!isdigit(ch)){ch=getchar();if(ch=='-')flag=-1;} while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*flag; } const db phi=acos(-1); int dcmp(db x) { if(fabs(x)<=eps)return 0; else return x>0?+1:-1; } struct vec { db x,y; vec(db xx=0,db yy=0){x=xx,y=yy;} db ang(){return atan2(y,x);} db len(){return sqrt(x*x+y*y);} vec operator+(vec a){return (vec){x+a.x,y+a.y};} vec operator-(vec a){return (vec){x-a.x,y-a.y};} vec operator*(db k){return (vec){x*k,y*k};} vec operator/(db k){return (vec){x/k,y/k};} bool operator==(vec a){return !dcmp(x-a.x)&&!dcmp(y-a.y);} }p[N]; typedef vec pot; db dot(vec a,vec b){return a.x*b.x+a.y*b.y;} db cross(vec a,vec b){return a.x*b.y-a.y*b.x;} struct line { pot s,t;db ang; line(pot ss=vec(),pot tt=vec()){s=ss;t=tt;ang=(tt-ss).ang();} }f[N]; bool cmp(line a,line b) { int k=dcmp(a.ang-b.ang); if(k)return k<0; else return dcmp(cross(a.t-a.s,b.t-a.s))<0; } bool pal(line a,line b) { return !dcmp(cross(a.t-a.s,b.t-b.s)); } pot get(line a,line b) { return a.s+(a.t-a.s)*(cross(b.t-b.s,a.s-b.s)/cross(a.t-a.s,b.t-b.s)); } bool onright(pot a,line l) { return dcmp(cross(a-l.s,l.t-l.s))>0; } pot Q[N]; line q[N]; db solve(int cnt) { int l=1,r=1;q[1]=f[1]; for(int i=2;i<=cnt;i++) if(dcmp(f[i].ang-f[i-1].ang)) { if(l<r&&(pal(q[l],q[l+1])||pal(q[r],q[r-1])))return 0; while(l<r&&onright(Q[r-1],f[i]))r--; while(l<r&&onright(Q[l],f[i]))l++; q[++r]=f[i];Q[r-1]=get(q[r-1],q[r]); } while(l<r&&onright(Q[r-1],q[l]))r--; while(l<r&&onright(Q[l],q[r]))l++; if(r-l<=1)return 0; Q[r]=get(q[l],q[r]); db ans=0; for(int i=l;i<=r;i++) { if(i!=r)ans+=cross(Q[i],Q[i+1]); else ans+=cross(Q[r],Q[l]); } return fabs(ans)/2.0; } int main() { int n=read(),cnt=0; for(int o=1;o<=n;o++) { int m=read(); for(int i=1;i<=m;i++) { p[i].x=read();p[i].y=read(); if(i!=1)f[++cnt]=(line){p[i-1],p[i]}; if(i==m)f[++cnt]=(line){p[i],p[1]}; } } f[++cnt]=(line){(pot){-inf,-inf},(pot){+inf,-inf}}; f[++cnt]=(line){(pot){+inf,-inf},(pot){+inf,+inf}}; f[++cnt]=(line){(pot){+inf,+inf},(pot){-inf,+inf}}; f[++cnt]=(line){(pot){-inf,+inf},(pot){-inf,-inf}}; sort(f+1,f+cnt+1,cmp); printf("%.3lf",solve(cnt)); return 0; }

转载于:https://www.cnblogs.com/Creed-qwq/p/10169605.html