poj 1228 Grandpa's Estate

题意：给定凸多边形上的一些点，问能否唯一确定一个凸多边形（可以加点使之变成另一凸多边形）。

分析：凸多边形的相邻两个顶点之间如果没有点，就有可能从外侧加一个点使之变成另一凸多边形，所以相邻两个顶点之间至少要有一个点，即每条边至少三个点。求出凸包的顶点，再枚举每条边的点数就可以了。

View Code

  1 /*
  2 Coder:Zhaofa Fang
  3 Lang:C++
  4 */
  5 #include <cstdio>
  6 #include <cstdlib>
  7 #include <iostream>
  8 #include <cmath>
  9 #include <cstring>
 10 #include <algorithm>
 11 #include <string>
 12 #include <vector>
 13 #include <queue>
 14 #include <stack>
 15 #include <map>
 16 #include <set>
 17 #define pb push_back
 18 using namespace std;
 19 
 20 //==========================================
 21 
 22 struct Point
 23 {
 24     double x,y;
 25 }point[1005],res[1005];
 26 
 27 double det(double x1,double y1,double x2,double y2)
 28 {
 29     return x1*y2-x2*y1;
 30 }
 31 double xmult(Point o,Point a ,Point b)
 32 {
 33     return det(a.x-o.x,a.y-o.y,b.x-o.x,b.y-o.y);
 34 }
 35 double getdis(Point a,Point b)
 36 {
 37     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
 38 }
 39 bool cmp(const Point &x,const Point &y)
 40 {
 41     if(xmult(point[0],x,y) == 0)
 42         return getdis(point[0],x)<getdis(point[0],y);
 43     return xmult(point[0],x,y) > 0;
 44 }
 45 bool Graham(int n)
 46 {
 47     if(n < 6)return false;
 48     Point tmp;
 49     int k=0,top=2;
 50     for(int i=1;i<n;i++)
 51     {
 52         if(point[i].y < point[k].y || point[i].y == point[k].y && point[i].x < point[k].x)
 53         k=i;
 54     }
 55     tmp=point[0],point[0]=point[k],point[k]=tmp;
 56     sort(point + 1 ,point + n , cmp);//极角排序
 57     res[0]=point[0],res[1]=point[1];
 58     for(int i=2;i<n;i++)
 59     {
 60         if(xmult(res[0],res[1],point[i]) == 0)
 61         {
 62             res[1]=point[i];
 63         }
 64         else
 65         {
 66             res[2]=point[i];
 67             k=i;
 68             break;
 69         }
 70     }
 71     for(int i=k+1;i<n;i++)
 72     {
 73         while(top && xmult(res[top-1],res[top],point[i])<=0)top--;
 74         res[++top]=point[i];
 75     }
 76     for(int i=1;i<=top;i++)
 77     {
 78         int cnt=0;
 79         for(int j=0;j<n;j++)
 80         {
 81             if(xmult(res[i-1],res[i],point[j])==0)cnt++;
 82         }
 83         if(cnt<3)return false;
 84     }
 85     return true;
 86 }
 87 int main()
 88 {
 89     int t;
 90     scanf("%d",&t);
 91     while(t--)
 92     {
 93         int n;
 94         scanf("%d",&n);
 95         for(int i=0;i<n;i++)
 96         {
 97             scanf("%lf%lf",&point[i].x,&point[i].y);
 98         }
 99         if(Graham(n))printf("YES\n");
100         else printf("NO\n");
101     }
102     return 0;
103 }