【BZOJ 2618】 2618: [Cqoi2006]凸多边形 (半平面交)

发布时间:2017-3-27 16:27:37 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"【BZOJ 2618】 2618: [Cqoi2006]凸多边形 (半平面交) ",主要涉及到【BZOJ 2618】 2618: [Cqoi2006]凸多边形 (半平面交) 方面的内容,对于【BZOJ 2618】 2618: [Cqoi2006]凸多边形 (半平面交) 感兴趣的同学可以参考一下。

 【分析】

  然而只是想做一道半平面交的模版题,就从星期二打到了现在。。。【下午还要考试呢真是无爱。。

  这题是求凸包的交,我们可以把每一条线段转化半平面,求半平面交。

  对于半平面交,最朴素的想法应该是两两线段求交点,然后判断是否在每一个平面内,然后求凸包吧(感觉奇慢无比啊)

  而事实上,如果有n的半平面的话,半平面交的答案那个凸包不会超过n条边,因为每个半平面最多只贡献一条边,说明我们事实上做了很多很多无用功。

  根据凸包的思想,我们觉得半平面交也是有单调性的。

  那个nlogn的算法可以看zzy的论文《半平面交的新算法及其实用价值》。

  半平面共用向量表示,向量的左边为有效半平面。

  定义半平面的极角为表示半平面的向量的极角。

  根据半平面的极角进行排序,若两个半平面极角相同,明显只需要保存最靠左的半平面,根据这个去重。

  然后这样做:

  

  

    

  跟单调队列差不多,两边判断,删减。

  

  注意最后还要判断一下,去尾。像这样:

  

  

  

  

  这题就是这样了。

放代码(调试很多,不删了)

  1 #include<cstdio>  2 #include<cstdlib>  3 #include<cstring>  4 #include<iostream>  5 #include<algorithm>  6 #include<cmath>  7 using namespace std;  8 #define Maxn 1100  9  10 struct P {double x,y;}; 11 struct L {P a,b;double slop;}l[Maxn]; 12 //半平面只方向向量a->b的左部分 13 //slop 极角 14 int cnt; 15  16 P operator - (P x,P y) 17 { 18     P tt; 19     tt.x=x.x-y.x; 20     tt.y=x.y-y.y; 21     return tt; 22 } 23  24 P operator + (P x,P y) 25 { 26     P tt; 27     tt.x=x.x+y.x; 28     tt.y=x.y+y.y; 29     return tt; 30 } 31  32 double Dot(P x,P y) {return x.x*y.x+x.y*y.y;} 33 double Cross(P x,P y) {return x.x*y.y-x.y*y.x;} 34 // bool operator < (L x,L y) {return x.slop<y.slop;} 35  36 bool operator < (L a,L b) 37 { 38     if(a.slop!=b.slop)return a.slop<b.slop; 39     return Cross(a.b-a.a,b.b-a.a)>0; 40 } 41  42 P operator * (P X,double y) 43 { 44     P tt; 45     tt.x=X.x*y; 46     tt.y=X.y*y; 47     return tt; 48 } 49  50 P a[Maxn]; 51 L q[Maxn]; 52 int tot; 53  54 P inter(L a,L b) 55 { 56     P X=a.a-a.b,Y=b.a-b.b,nw; 57     double tt; 58     nw=b.a-a.a; 59     tt=Cross(nw,X)/Cross(X,Y); 60     P ans=b.a+Y*tt; 61     return ans; 62 } 63  64 bool jud(L a,L b,L c) 65 { 66     P p=inter(a,b); 67     return Cross(c.b-c.a,p-c.a)<0; 68 } 69  70 void opp() 71 { 72     for(int i=1;i<=cnt;i++) 73     { 74         printf("%.2lf %.2lf %.2lf %.2lf = %.2lf \n",l[i].a.x,l[i].a.y,l[i].b.x,l[i].b.y,l[i].slop); 75     } 76     printf("\n"); 77 } 78  79 void output() 80 { 81     for(int i=1;i<=tot;i++) printf("%2lf %.2lf\n",a[i].x,a[i].y); 82     printf("\n"); 83 } 84  85 void op(int L,int R) 86 { 87     for(int i=L;i<=R;i++) 88         printf("%lf %lf %lf %lf\n",l[i].a.x,l[i].a.y,l[i].b.x,l[i].b.y); 89     printf("\n"); 90 } 91  92 void ffind() 93 { 94     for(int i=1;i<=cnt;i++) 95       l[i].slop=atan2(l[i].b.y-l[i].a.y,l[i].b.x-l[i].a.x); 96     sort(l+1,l+1+cnt); 97      98     // opp(); 99     100     int L=1,R=0;101     //去重?102     tot=0;103     for(int i=1;i<=cnt;i++)104     {105         if(l[i].slop!=l[i-1].slop) tot++;106         l[tot]=l[i];107     }108     cnt=tot;tot=0;109     // opp();110     q[++R]=l[1];q[++R]=l[2];111     for(int i=3;i<=cnt;i++)112     {113         while(L<R&&jud(q[R-1],q[R],l[i])) R--;114         while(L<R&&jud(q[L+1],q[L],l[i])) L++;115         q[++R]=l[i];116         // op(L,R);117     }118     while(L<R&&jud(q[R-1],q[R],q[L])) R--;119     while(L<R&&jud(q[L+1],q[L],q[R])) L++;120     q[R+1]=q[L];121     for(int i=L;i<=R;i++)122       a[++tot]=inter(q[i],q[i+1]);123   // output();124   125   // output();126 }127 128 void init()129 {130     int n;131     /*scanf("%d",&n);132     for(int i=1;i<=n;i++)133     {134         scanf("%lf%lf%lf%lf\n",&l[i].a.x,&l[i].a.y,&l[i].b.x,&l[i].b.y);135     }136     cnt=n;*/137     scanf("%d",&n);138     cnt=0;139     for(int i=1;i<=n;i++)140     {141         int m;142         scanf("%d",&m);143         P ft,now;144         scanf("%lf%lf",&ft.x,&ft.y);145         now=ft;146         for(int j=2;j<=m;j++)147         {148             P nw;149             scanf("%lf%lf",&nw.x,&nw.y);150             l[++cnt].b=nw;151             l[cnt].a=now;152             now=nw;153         }154         l[++cnt].a=now;l[cnt].b=ft;155     // opp();156     }157     158     159     for(int i=1;i<=cnt;i++)160       l[i].slop=atan2(l[i].b.y-l[i].a.y,l[i].b.x-l[i].a.x);161     // opp();162     163 }164 165 void get_area()166 {167     double ans=0;168     for(int i=1;i<tot;i++)169     {170         ans+=Cross(a[i],a[i+1]);171     }172     ans+=Cross(a[tot],a[1]);173     if(tot<3) ans=0;174     printf("%.3lf\n",ans/2);175 }176 177 int main()178 {179     init();180     ffind();181     // output();182     get_area();183     return 0;184 }
View Code

用向量法求两直线的交点:

本质就是用面积比表示线段比。

P inter(L a,L b){	P X=a.a-a.b,Y=b.a-b.b,nw;	double tt;	nw=b.a-a.a;	tt=Cross(nw,X)/Cross(X,Y);	P ans=b.a+Y*tt;	return ans;}

半平面交核心过程:

q[++R]=l[1];q[++R]=l[2];for(int i=3;i<=cnt;i++){	while(L<R&&jud(q[R-1],q[R],l[i])) R--;	while(L<R&&jud(q[L+1],q[L],l[i])) L++;	q[++R]=l[i];}if(L<R&&jud(q[R-1],q[R],q[L])) R--;

 

代码的具体实现其实没有分上壳和下壳,是一起做的,每次保存有用的半平面,最后相邻的求交点形成凸包。

最后也不用处理上面去尾的情况了,但是注意加一句if,判断最后加的那个半平面是有效的。

if(L<R&&jud(q[R-1],q[R],q[L])) R--;

【倒是对几何画板越来越熟练了,捂脸= =

2016-12-24 09:48:20

上一篇:E. Santa Claus and Tangerines
下一篇:什么是API

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款