题意：
给定一个多边形，让你求出其价值。价值的定义是：-p*凹面的个数+q*凸面的个数。。。。
（其实参照了这个博客，才理解题意。。。。http://blog.csdn.net/juststeps/article/details/8666769）
凸面的个数就是凸包中的点的个数，但是当出现凹面时，就会减少一个凸面，这是因为这时候的凸面是虚拟出来的！！！！！
View Code
1 /* 2 凸包 3 */ 4 #include<stdio.h> 5 #include<string.h> 6 #include<stdlib.h> 7 #include<algorithm> 8 #include<iostream> 9 #include<queue> 10 //#include<map> 11 #include<math.h> 12 using namespace std; 13 typedef long long ll; 14 //typedef __int64 int64; 15 const int maxn = 35; 16 const int inf = 0x7fffffff; 17 const double pi=acos(-1.0); 18 struct node{ 19 int x,y,num; 20 bool operator <( const node & p ) const { 21 return y<p.y||(y==p.y&&x<p.x); 22 } 23 }; 24 node pnt[ maxn ],res[ maxn ]; 25 int cross( node sp,node ep,node op ){ 26 return ( sp.x-op.x )*( ep.y-op.y )-( sp.y-op.y )*( ep.x-op.x ); 27 } 28 int dis2( node a,node b ){ 29 return ( a.x-b.x )*( a.x-b.x )+( a.y-b.y )*( a.y-b.y ); 30 } 31 int garham( int n ){ 32 int top=1; 33 sort( pnt,pnt+n ); 34 35 if( n==0 ) return 0; 36 else res[ 0 ]=pnt[ 0 ]; 37 if( n==1 ) return 1; 38 else res[ 1 ]=pnt[ 1 ]; 39 if( n==2 ) return 2; 40 else res[ 2 ]=pnt[ 2 ]; 41 42 for( int i=2;i<n;i++ ){ 43 while( top>0&&cross( res[ top ],res[ top-1 ],pnt[ i ] )>=0 ) 44 top--; 45 res[ ++top ]=pnt[ i ]; 46 } 47 48 int len=top; 49 res[ ++top ]=pnt[ n-2 ]; 50 51 for( int i=n-3;i>=0;i-- ){ 52 while( top!=len&&cross( res[ top ],res[ top-1 ],pnt[ i ] )>=0 ) 53 top--; 54 res[ ++top ]=pnt[ i ]; 55 } 56 57 return top; 58 } 59 60 int main(){ 61 int ca; 62 scanf("%d",&ca); 63 while( ca-- ){ 64 int p,q,n; 65 scanf("%d%d%d",&p,&q,&n); 66 for( int i=0;i<n;i++ ){ 67 scanf("%d%d",&pnt[ i ].x,&pnt[ i ].y); 68 pnt[ i ].num = i; 69 } 70 int vis[ maxn ]; 71 memset( vis,0,sizeof( vis ) ); 72 int cnt=garham( n );//凸包中点的个数 73 for( int i=0;i<cnt;i++ ) 74 vis[ res[ i ].num ]=1;//用来标记凸包上的点 75 int dent = 0; 76 vis[ n ]=vis[ 0 ]; 77 for( int i=0;i<n;i++ ){ 78 if( vis[ i ]==1&&vis[ i+1 ]==0 ) 79 dent++; 80 }//这个很巧妙的找到了凹面！！！！！！！！！！ 81 82 //printf("%d %d\n",dent,cnt); 83 int ans = ( (-1)*p )*dent+( cnt-dent )*q; 84 printf("%d\n",ans>0?ans:0); 85 } 86 return 0; 87 }