HDU2907凸包+凹面-白红宇

HDU2907凸包+凹面

阅读量：5024 次

发布时间：2019-06-12

本文共 1189 字，大约阅读时间需要 3 分钟。

题意：

给定一个多边形，让你求出其价值。价值的定义是：-p*凹面的个数+q*凸面的个数。。。。

（其实参照了这个博客，才理解题意。。。。http://blog.csdn.net/juststeps/article/details/8666769）

凸面的个数就是凸包中的点的个数，但是当出现凹面时，就会减少一个凸面，这是因为这时候的凸面是虚拟出来的！！！！！

View Code

1 /* 2 凸包 3 */ 4 #include
      
        5 #include
       
         6 #include
        
          7 #include
         
           8 #include
          
            9 #include
           
            10 //#include
            11 #include
             
              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
              
               
                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
                
                 0?ans:0);85 }86 return 0;87 }