首页 > 代码库 > BZOJ 1137 半平面交
BZOJ 1137 半平面交
半平面交的板子
//By SiriusRen#include <bits/stdc++.h>#define double long doubleusing namespace std;const int N=100050;const double eps=1e-10;int n,m,xx,yy,tot;double Ans;vector<int>vec[N];struct Point{double x,y;}point[N];struct Line{Point a,b;double angle;}line[N],q[N];void addline(Line &l,Point a,Point b){ l.a=a,l.b=b,l.angle=atan2(b.y-a.y,b.x-a.x);}Point operator-(Point a,Point b){ Point c;c.x=a.x-b.x,c.y=a.y-b.y;return c;}double operator*(Point a,Point b){ return a.x*b.y-a.y*b.x;}bool operator<(Line a,Line b){ if(a.angle==b.angle)return (b.b-a.a)*(b.a-a.a)>0; return a.angle<b.angle;}Point inter(Line a,Line b){ double k1,k2,t; k1=(a.b-b.a)*(b.b-b.a); k2=(b.b-b.a)*(a.a-b.a); t=k1/(k1+k2); Point ans; ans.x=a.b.x+(a.a.x-a.b.x)*t; ans.y=a.b.y+(a.a.y-a.b.y)*t; return ans;}double dis(Point x,Point y){ x=y-x; return sqrt(x.x*x.x+x.y*x.y);}bool judge(Line a,Line b,Line t){ Point p=inter(a,b); return (t.a-p)*(t.b-p)<0;}void bpmj(){ sort(line+1,line+1+tot); n=0; for(int i=1;i<=tot;i++){ if(abs(line[i].angle-line[i-1].angle)>eps)n++; line[n]=line[i]; } int r=1,l=0; q[0]=line[1],q[1]=line[2]; for(int i=3;i<=n;i++){ while(l<r&&judge(q[r],q[r-1],line[i]))r--; while(l<r&&judge(q[l],q[l+1],line[i]))l++; q[++r]=line[i]; } while(l<r&&judge(q[r],q[r-1],q[l]))r--; while(l<r&&judge(q[l],q[l+1],q[r]))l++; q[r+1]=q[l],tot=0; for(int i=l;i<=r;i++)point[++tot]=inter(q[i],q[i+1]); point[++tot]=point[1]; for(int i=1;i<tot;i++)Ans+=dis(point[i],point[i+1]);}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%Lf%Lf",&point[i].x,&point[i].y); Ans=-dis(point[1],point[n]); for(int i=1;i<=m;i++){ scanf("%d%d",&xx,&yy); if(xx>yy)swap(xx,yy); vec[xx].push_back(yy); } for(int i=1,j,k;i<=n;i++){ sort(vec[i].begin(),vec[i].end()); for(j=n,k=vec[i].size()-1;j>i&&~k;j--,k--) if(vec[i][k]!=j)break; if(i==1&&j==n){printf("%.10Lf\n",dis(point[1],point[n]));return 0;} if(j>i)addline(line[++tot],point[j],point[i]); }addline(line[++tot],point[1],point[n]); bpmj(); printf("%.10Lf\n",Ans);}
BZOJ 1137 半平面交
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。