POJ1228+凸包

见代码。
  1 /*
  2 凸包（稳定凸包）
  3 题意：给出一些点，这些点要么是凸包的顶点要么是边上的。
  4 证明每条边上都至少有3个点。
  5 */
  6 #include<stdio.h>
  7 #include<string.h>
  8 #include<stdlib.h>
  9 #include<algorithm>
 10 #include<iostream>
 11 #include<queue>
 12 #include<map>
 13 #include<stack>
 14 #include<set>
 15 #include<math.h>
 16 using namespace std;
 17 typedef long long int64;
 18 //typedef __int64 int64;
 19 typedef pair<int64,int64> PII;
 20 #define MP(a,b) make_pair((a),(b)) 
 21 const int maxn = 1005;
 22 const int inf = 0x7fffffff;
 23 const double pi=acos(-1.0);
 24 const double eps = 1e-8;
 25 
 26 struct Point {
 27     double x,y;
 28     bool operator < ( const Point p ) const {
 29         return y<p.y||(y==p.y&&x<p.x);
 30     }
 31 }res[ maxn ],pnt[ maxn ];
 32 bool flag[ maxn ][ maxn ];//f[i][j]:点ij之间是否还有点
 33 bool ok[ maxn ];//ok[i]:i是否是凸包的顶点
 34 
 35 double xmult( Point sp,Point ep,Point op ){
 36     return (sp.x-op.x)*(ep.y-op.y)-(sp.y-op.y)*(ep.x-op.x);
 37 }
 38 
 39 double dis2( Point a,Point b ){
 40     return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
 41 }
 42 
 43 double dis( Point a,Point b ){
 44     return sqrt( dis2(a,b) );
 45 } 
 46 
 47 bool PointOnLine( Point a,Point L,Point R ){
 48     return ( fabs(xmult( a,L,R ))<eps )&&( (a.x-L.x)*(a.x-R.x)<eps )&&( (a.y-L.y)*(a.y-R.y)<eps );
 49 }
 50 
 51 int Garham( int n ){
 52     int top = 1;
 53     sort( pnt,pnt+n );
 54     if( n==0 ) return 0;
 55     else res[ 0 ] = pnt[ 0 ];
 56     if( n==1 ) return 1;
 57     else res[ 1 ] = pnt[ 1 ];
 58     if( n==2 ) return 2;
 59     else res[ 2 ] = pnt[ 2 ];
 60     for( int i=2;i<n;i++ ){
 61         while( top>0&&xmult( res[top],res[top-1],pnt[i] )>=0 )
 62             top--;
 63         res[ ++top ] = pnt[ i ];
 64     }
 65     int tmp = top;
 66     res[ ++top ] = pnt[ n-2 ];
 67     for( int i=n-3;i>=0;i-- ){
 68         while( top!=tmp&&xmult( res[top],res[top-1],pnt[i] )>=0 )
 69             top--;
 70         res[ ++top ] = pnt[ i ];
 71     }
 72     return top;
 73 }
 74 
 75 int main(){
 76     int T;
 77     scanf("%d",&T);
 78     while( T-- ){
 79         int n;
 80         scanf("%d",&n);
 81         for( int i=0;i<n;i++ )
 82             scanf("%lf%lf",&pnt[i].x,&pnt[i].y);
 83         if( n<=5 ){
 84             puts("NO");
 85             continue;
 86         }//至少要6个点
 87         int cnt = Garham( n );
 88         memset( ok,false,sizeof( ok ) );
 89         memset( flag,false,sizeof( flag ) );
 90         for( int i=0;i<n;i++ ){
 91             for( int j=0;j<cnt;j++ ){
 92                 if( pnt[i].x==res[j].x&&pnt[i].y==res[j].y ){
 93                     ok[ i ] = true;
 94                     break;
 95                 }
 96             }
 97         }
 98         for( int i=0;i<n;i++ ){
 99             if( !ok[i] ){
100                 for( int j=0;j<cnt;j++ ){
101                     if( PointOnLine( pnt[i],res[j],res[(j+1)%cnt]) ){
102                         flag[ j ][ (j+1)%cnt ] = true;
103                     }
104                 }
105             }
106         }
107         bool ans = true;
108         for( int i=0;i<cnt;i++ ){
109             if( flag[ i ][ (i+1)%cnt ]==false ){
110                 ans = false;
111                 break;
112             }
113         }
114         if( ans ) printf("YES
");
115         else puts("NO");
116     }
117     return 0;
118 }
View Code
keep moving...