半平面交求多边形的核, 注意边是顺时针给出的
- // 卡精致死于是换 (?) 了一种求半平面交的方法
- #include<iostream>
- #include<cstdio>
- #include<algorithm>
- #include<cmath>
- using namespace std;
- const int N=505;
- int n,cas;
- const double eps=1e-8;
- struct dian
- {
- double x,y;
- dian(double X=0,double Y=0)
- {
- x=X,y=Y;
- }
- dian operator + (const dian &a) const
- {
- return dian(x+a.x,y+a.y);
- }
- dian operator - (const dian &a) const
- {
- return dian(x-a.x,y-a.y);
- }
- dian operator * (const double &a) const
- {
- return dian(x*a,y*a);
- }
- dian operator / (const double &a) const
- {
- return dian(x/a,y/a);
- }
- }a[N],p[N];
- struct bian
- {
- dian s,v;//s 表示向量的起点, v 表示向量的方向和长度 (从(0,0) 射出)
- double a;
- bian(dian S=dian(),dian V=dian())
- {
- s=S,v=V;
- a=atan2(v.y,v.x);
- }
- }l[N],s[N];
- int sgn(double x)
- {
- return x<-eps?-1:x>eps;
- }
- double cj(dian a,dian b)// 叉积
- {
- return a.x*b.y-a.y*b.x;
- }
- double mj(dian a,dian b,dian c)// 求有向面积
- {
- return cj(b-a,c-a)/2.0;
- }
- dian jd(bian x,bian y)// 求交点
- {
- return x.s+x.v*(cj(x.s-y.s,y.v)/cj(y.v,x.v));
- }
- dian nor(dian a)
- {
- return dian(-a.y,a.x);
- }
- bool px(bian x,bian y)// 判断平行
- {
- return sgn(cj(y.v,x.v))==0;
- }
- bool bn(bian x,bian y)//x 在 y 的逆时针方向(平行先左后右
- {
- double ar=cj(x.v,y.v);
- return (sgn(ar)>0)||((sgn(ar)==0)&&sgn(cj(x.v,y.s-x.s))>0);
- }
- bool dn(dian x,bian y)// 点在线的逆时针方向
- {
- return sgn(cj(y.v,x-y.s))>0;
- }
- bool cmp(const bian &x,const bian &y)// 极角排序
- {
- // if(sgn(x.v.y)==0&&sgn(y.v.y)==0)// 同与 x 轴平行
- // return x.v.x<y.v.x;
- // if((sgn(x.v.y)<=0)==(sgn(y.v.y)<=0))// 同在 x 轴上或下(包括 x 轴)
- // return bn(x,y);
- // return x.v.y<y.v.y;// 一上一下下在前
- return sgn(x.a-y.a)==-1;
- }
- dian ite(bian a,bian b)
- {
- return a.s+a.v*(cj(b.v,a.s-b.s)/cj(a.v,b.v));
- }
- int main()
- {
- while(scanf("%d",&n)&&n)
- {
- for(int i=0;i<n;i++)
- scanf("%lf%lf",&p[i].x,&p[i].y);
- p[n]=p[0];
- for(int i=0;i<n;i++)
- l[i]=bian(p[i]-nor(p[i]-p[i+1])*eps,p[i]-p[i+1]);
- sort(l,l+n,cmp);
- int ll=0,rr=0;
- s[rr++]=l[0];
- for(int i=1;i<n;i++)// 每次新加入向量, 就会删掉在向量右边的交点(线上的也要删), 维护的凸包首尾都是要删除的, 最后还要模拟插入队头, 把队尾中多余的半平面去掉
- {
- while(ll+1<rr&&!dn(p[rr-2],l[i]))
- rr--;
- while(ll+1<rr&&!dn(p[ll],l[i]))
- ll++;
- s[rr++]=l[i];
- if(ll+1<rr&&sgn(cj(s[rr-1].v,s[rr-2].v))==0)
- {
- rr--;
- if(dn(l[i].s,s[rr-1]))
- s[rr-1]=l[i];
- }
- if(ll+1<rr)
- p[rr-2]=ite(s[rr-1],s[rr-2]);
- }
- while(ll+1<rr&&!dn(p[rr-2],s[ll]))
- rr--;//cout<<rr<<endl;
- if(rr-ll>1)
- printf("Floor #%d\nSurveillance is possible.\n",++cas);
- else
- printf("Floor #%d\nSurveillance is impossible.\n",++cas);
- printf("\n");
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2517923.html