hdu3685（几何重心与凸包结合） - c++编程基础

题意：给一个多边形（有可能是凹多边形）。问有多少种能够使得它稳定放置的方式。当然稳定的原则就是重心做垂线在支撑点之内。

解法：因为有可能是凹多边形，所以先求出多边形的凸包，这是在放置时候会接触地面的所有点。然后将重心与每天凸边判断是否稳定；

代码：

/******************************************************
* @author:xiefubao
*******************************************************/
#pragma comment(linker, "/STACK:102400000,102400000")
#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
           #include 
           
             #include 
            
              //freopen ("in.txt" , "r" , stdin); using namespace std; #define eps 1e-8 #define zero(_) (_<=eps) const double pi=acos(-1.0); typedef long long LL; const int Max=100010; const LL INF=0x3FFFFFFF; struct point { double x,y; }; point points[50005]; point focus; int top; int stack[50005]; int N; double mult(point a,point b,point c) { a.x-=c.x; a.y-=c.y; b.x-=c.x; b.y-=c.y; return a.x*b.y-a.y*b.x; } double dis(const point& a,const point& b) { return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); } bool operator<(point a,point b) { if(mult(a,b,points[0])>0||(mult(a,b,points[0])==0 && a.x
             
              r&&r+u>l) ans++; } double l=dis(focus,points[stack[top]]); double r=dis(focus,points[stack[0]]); double u=dis(points[stack[top]],points[stack[0]]); if(l+u>r&&r+u>l) ans++; return ans; } void graham(int n) { int mi=0; for(int i=1; i
              
               0&&mult(points[stack[top]],points[stack[top-1]],points[i])>=0) { top--; } stack[++top]=i; } } int main() { int t; cin>>t; while(t--) { scanf("%d",&N); for(int i=0; i