【POJ 3335】 Rotating Scoreboard （多边形的核- - 半平面交应用）

 

【分析】

　　一个比较好的多边形的核的求法的解答：http://www.cnblogs.com/ka200812/archive/2012/01/20/2328316.html

 

　　把原题转换成半平面的交，看看是否为空集。

　　可以参考一下这个图：

　　

圈起来的是原多边形的顶点，其他是辅助线和辅助点，阴影部分是多边形的核。

 

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 #define Maxn 100010

 const double eps=0.0001;

 const double pi=3.141592653;

 struct P {double x,y;};

 struct L {P a,b;double slop;}l[Maxn],p[Maxn];

 int len;

 double Dot(P x,P y) {return x.x*y.x+x.y*y.y;}

 double Cross(P x,P y) {return x.x*y.y-x.y*y.x;}

 P operator - (P x,P y)

 {

     P tt;

     tt.x=x.x-y.x;

     tt.y=x.y-y.y;

     return tt;

 }

 P operator + (P x,P y)

 {

     P tt;

     tt.x=x.x+y.x;

     tt.y=x.y+y.y;

     return tt;

 }

 P operator * (P x,double y)

 {

     P tt;

     tt.x=x.x*y;

     tt.y=x.y*y;

     return tt;

 }

 bool operator < (L x,L y) {return (x.slop==y.slop)?(Cross(x.b-x.a,y.b-x.a)<):(x.slop<y.slop);}

 P inter(L x,L y)

 {

     P nw=y.a-x.a;

     P X=x.b-x.a,Y=y.b-y.a;

     double tt;

     tt=Cross(nw,X)/Cross(X,Y);

     return y.a+Y*tt;

 }

 bool jud(L x,L y,L z)

 {

     // if(x.slop==-y.slop) return 1;

     // if(x.slop-pi-y.slop<=eps&&x.slop-pi-y.slop>=-eps) return 1;

     // if(y.slop-pi-x.slop<=eps&&y.slop-pi-x.slop>=-eps) return 1;

     //???????

     P nw=inter(x,y);

     return Cross(z.b-z.a,nw-z.a)<;

 }

 int cnt;

 void op()

 {

     for(int i=;i<=cnt;i++)

     {

         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);

     }

     printf("\n");

 }

 void opp(int L,int R)

 {

     for(int i=L;i<=R;i++)

     {

         printf("%.2lf %.2lf %.2lf %.2lf = %.2lf\n",p[i].a.x,p[i].a.y,p[i].b.x,p[i].b.y,p[i].slop);

     }

     printf("\n");

 }

 void ffind()

 {

     sort(l+,l++cnt);

     // op();

     int tot=;

     for(int i=;i<=cnt;i++)

     {

         if(l[i].slop!=l[tot].slop) l[++tot]=l[i];

     }

     cnt=tot;

     if(cnt<=) {printf("NO\n");return;}

     // op();

     p[]=l[];p[]=l[];

     int L=,R=;

     for(int i=;i<=cnt;i++)

     {

         while(R>L&&jud(p[R],p[R-],l[i])) R--;

         while(R>L&&jud(p[L],p[L-],l[i])) L++;

         p[++R]=l[i];

     }

     // if(R>L&&jud(p[L],p[L+1],p[R])<0) R--;

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

     // opp(L,R);

     if(R-L+<=) printf("NO\n");

     else printf("YES\n");

 }

 int main()

 {

     int T;

     scanf("%d",&T);

     while(T--)

     {

         int n;

         scanf("%d",&n);

         P now,ft;

         scanf("%lf%lf",&ft.x,&ft.y);

         now=ft;

         cnt=;

         for(int i=;i<=n;i++)

         {

             P nw;

             scanf("%lf%lf",&nw.x,&nw.y);

             l[++cnt].a=nw;l[cnt].b=now;

             now=nw;

         }

         l[++cnt].a=ft;l[cnt].b=now;

         for(int i=;i<=cnt;i++) l[i].slop=atan2(l[i].b.x-l[i].a.x,l[i].b.y-l[i].a.y);

         // op();

         ffind();

     }

     return ;

 }

2016-12-26 18:51:45