●POJ 3348 Cows

题链：

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

题解：

计算几何，凸包，多边形面积

好吧，就是个裸题，没什么可讲的。

代码：

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define MAXN 10050

using namespace std;

const double eps=1e-8;

int sign(double x){

	if(fabs(x)<=eps) return 0;

	return x<0?-1:1;

}

struct Point{

	double x,y;

	Point(double _x=0,double _y=0):x(_x),y(_y){}

	void Read(){scanf("%lf%lf",&x,&y);}

};

typedef Point Vector;

bool operator < (Point A,Point B){return sign(A.x-B.x)<0||(sign(A.x-B.x)==0&&sign(A.y-B.y)<0);}

bool operator == (Point A,Point B){return sign(A.x-B.x)==0&&sign(A.y-B.y)==0;}

Vector operator + (Vector A,Vector B){return Vector(A.x+B.x,A.y+B.y);}

Vector operator - (Point A,Point B){return Vector(A.x-B.x,A.y-B.y);}

double operator ^ (Vector A,Vector B){return A.x*B.y-A.y*B.x;}

Point D[MAXN],H[MAXN];

int Andrew(int dnt){

	int hnt=0,k=0;

	sort(D+1,D+dnt+1);

	dnt=unique(D+1,D+dnt+1)-D-1;

	for(int i=1;i<=dnt;i++){

		while(hnt>1&&sign((H[hnt]-H[hnt-1])^(D[i]-H[hnt-1]))<=0) hnt--;

		H[++hnt]=D[i];

	} k=hnt;

	for(int i=dnt-1;i>=1;i--){

		while(hnt>k&&sign((H[hnt]-H[hnt-1])^(D[i]-H[hnt-1]))<=0) hnt--;

		H[++hnt]=D[i];

	}

	return hnt;

}

double GCPA(int hnt){//Get_Convex_Polygon_Area

	double S=0;

	for(int i=1;i<hnt;i++) S+=(H[i]^H[i+1])/2;

	return S;

}

int main(){

	int N; scanf("%d",&N);

	for(int i=1;i<=N;i++) D[i].Read();

	printf("%d",(int)(GCPA(Andrew(N))/50));

	return 0;

}