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

题目来源：

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 <iostream>
#include <algorithm>
#include <stdlib.h>
#include <iostream>
#include <stdio.h>
#include <stack>
#include <string>
#include <string.h>
#include <algorithm>
#include <stdlib.h>
#include <vector>
#include <set>
#include <math.h>
#include <cmath>
#include <map>
#include <queue>
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]) <b.dist(List[0])  ) return 1;
    return 0;
}
void init(int n)
{
    for(int i=0 ; i<n ;i++)
        cin>>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
",(int)sum/50);
    return 0;
}