poj 3348 Cows 求凸包以及凸包的面积-白红宇

poj 3348 Cows 求凸包以及凸包的面积

阅读量：6251 次

发布时间：2019-06-22

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

题目来源：

http://poj.org/problem?id=3348

1:任意多边形p[0,n-1]的面积为

for(int i=0 ; i<=n-1 ; i++){

sum+= (sk[i]^sk[(i+1)%(n) ] )*0.5;

}

2: 求凸包，用graham 模板

代码如下：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   #include 
                    
                     using namespace std ;typedef long long LL;const int N = 10010;double EPS= 1e-10;double add(double a, double b){ if( fabs(a+b)< EPS * ( fabs(a)+fabs(b) ) ) return 0; return a+b;}struct Point{ double x,y; Point(){} Point(double _x, double _y):x(_x),y(_y){} Point operator + (Point p){ return Point( add(x,p.x), add( y,p.y ) ); } Point operator -(Point p){ return Point( add(x,-p.x), add(y, -p.y) ); } double operator^(Point p){ return add(x*p.y, -y*p.x ); } friend istream& operator>>(istream& is, Point& p){ is>>p.x>>p.y; return is; } double dist(Point p){ return sqrt( add( ( x-p.x)*(x-p.x) , (y-p.y)*(y-p.y) ) ); }};Point List[N]; // 点集int top; // 栈顶指针Point sk[N]; // 栈bool cmp(Point a, Point b) // 按y轴值从小到大， y轴值相同时，x轴从小到大排列{ if(a.y != b.y) return a.y < b.y; else return a.x < b.x;}bool operator < (Point a, Point b) // 极角排序{ double tmp= (a-List[0])^(b-List[0]); if(tmp > 0) return 1; else if(tmp== 0 && a.dist(List[0]) 
                     
                      >List[i]; sort(List, List+n,cmp);// 排序后 List[0]为最左下方的点 sort(List+1 , List+n ); // 对List[1,n-1] 中的点进行极角排序，为凸包做准备}void graham(int n){ sk[0]=List[0]; sk[1]=List[1]; top=1; double t; for(int i=2 ; i< n ; i++){ while(top >= 1 && ( (sk[top]-sk[top-1] )^(List[i]-sk[top-1] ) ) <=0 ) top--; // 不是凸包中的点出栈 top++;// 点i进栈 sk[top]=List[i]; }}int main(){ int n; cin>>n; init(n); graham(n); double sum=0.0; for(int i=0 ; i<=top ; i++){ sum+= (sk[i]^sk[(i+1)%(top+1) ] )*0.5; } printf("%d\n",(int)sum/50); return 0;}