首页 > 代码库 > BZOJ 2618 CQOI2006 凸多边形 半平面交
BZOJ 2618 CQOI2006 凸多边形 半平面交
题目大意:给定n个凸多边形,求交集的面积
时隔多年我终于把完整的半平面交搞出来了……真尼玛艰辛……
曾经写了一发 RE到死 于是就搁置0.0 今天写一发又是WA到死的节奏……
不多说直接上代码 其实刘汝佳同学写麻烦了 每次插入一个半平面之后不用两端都删的 只删一端 最后再处理两端的部分就行
300题留念……切了道模板题也不错
#include <cmath> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 510 #define EPS 1e-7 using namespace std; struct point{ double x,y; point(){} point(double _,double __): x(_),y(__){} point operator + (const point &p) const { return point(x+p.x,y+p.y); } point operator - (const point &p) const { return point(x-p.x,y-p.y); } double operator * (const point &p) const { return x*p.y-y*p.x; } point operator * (const double &rate) const { return point(x*rate,y*rate); } void Read() { scanf("%lf%lf",&x,&y); } }points[M]; struct line{ point p,v; double alpha; line(){} line(const point &p1,const point &p2):p(p1),v(p2-p1) { alpha=atan2(v.y,v.x); } bool operator < (const line &l) const { return alpha < l.alpha; } }lines[M]; int n,m,tot; line *q[M]; int r,h; double ans; bool Onleft(const point &p,const line &l) { return (l.p-p)*l.v>=0; } point Get_Intersection(const line &l1,const line &l2) { point u=l1.p-l2.p; double temp=(l2.v*u)/(l1.v*l2.v); return l1.p+l1.v*temp; } void Get_Half_Plane_Intersection() { int i; for(i=1;i<=tot;i++) { while( r-h>=2 && !Onleft(Get_Intersection(*q[r],*q[r-1]),lines[i]) ) q[r--]=0x0; if( r-h>=1 && fabs(lines[i].v*q[r]->v)<=0 ) q[r]=Onleft(lines[i].p,*q[r])?&lines[i]:q[r]; else q[++r]=&lines[i]; } while( r-h>=2 && !Onleft(Get_Intersection(*q[h+1],*q[h+2]),*q[r]) ) q[++h]=0x0; while( r-h>=2 && !Onleft(Get_Intersection(*q[r],*q[r-1]),*q[h+1]) ) q[r--]=0x0; } int main() { int i,j; cin>>n; for(i=1;i<=n;i++) { point first,p1,p2; scanf("%d",&m); first.Read();p2=first; for(j=2;j<=m;j++) { p1=p2;p2.Read(); lines[++tot]=line(p1,p2); } lines[++tot]=line(p2,first); } sort(lines+1,lines+tot+1); Get_Half_Plane_Intersection(); if(r-h<=2) return puts("0.000"),0; tot=0; for(i=h+2;i<=r;i++) points[++tot]=Get_Intersection(*q[i],*q[i-1]); points[++tot]=Get_Intersection(*q[r],*q[h+1]); for(i=2;i<=tot;i++) ans+=points[i-1]*points[i]; ans+=points[tot]*points[1]; printf("%.3lf\n",ans/2); return 0; }
BZOJ 2618 CQOI2006 凸多边形 半平面交
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。