题目链接：
http://poj.org/problem?id=3348
思路：
先对点进行排序，然后求出凸包。对凸包上的点进行面积计算，即将多边形面积分成多个三角形，利用叉积计算即可。
代码：
#include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> #define PI acos(-1.0) #define eps 0.00000001 using namespace std; struct Point{ double x,y; Point(double x=0,double y=0):x(x),y(y){} }; struct line{ Point a,b; line(Point a=0,Point b=0):a(a),b(b){} }; Point p[10005],ch[10005]; line Line[5005]; Point operator + (Point A ,Point B){ return Point(A.x+B.x,A.y+B.y); } Point operator - (Point A,Point B){ return Point(A.x-B.x,A.y-B.y); } Point operator * (Point A,double p){ return Point(A.x*p,A.y*p); } bool operator < (const Point &a,const Point &b){ return a.x<b.x||(a.x==b.x&&a.y<b.y); } int dcmp(double x){ if(fabs(x)<eps)return 0; else if(x<0)return -1; return 1; } bool operator ==(const Point &a,const Point &b){ return dcmp(a.x-b.x)==0&&dcmp(a.y-b.y)==0; } double Dot(Point A,Point B){ return A.x*B.x+A.y*B.y; } double Cross(Point A,Point B){ return A.x*B.y-A.y*B.x; } double Length(Point A){ return sqrt(Dot(A,A)); } double getdistance(Point P,line A){ Point v1=A.b-A.a; Point v2=P-A.a; return fabs(Cross(v1,v2)/Length(v1)); } int LeftofLine(Point P,line A){ Point c1,c2; c1=A.a; c2=A.b; double tmp=(c1.x-c2.x)/(c1.y-c2.y)*(P.y-c2.y)+c2.x; if(tmp>P.x)return 1; else if(tmp<P.x)return 2; else return 4; } bool cmp(Point A ,Point B){ if(A.x==B.x)return A.y<B.y; return A.x<B.x; } int ConvexHull(Point *p,int n,Point *ch){ sort(p,p+n); int m=0; for(int i=0;i<n;i++) { while(m>1&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-1])<=0) m--; ch[m++]=p[i]; } int k=m; for(int i=n-1;i>=0;i--) { while(m>k&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-1])<=0) m--; ch[m++]=p[i]; } if(n) m--; return m; } int main(){ int n; int T; double x1,y1,x2,y2; while(~scanf("%d",&n)){ for(int i=0;i<n;i++){ scanf("%lf%lf",&x1,&y1); p[i]=Point(x1,y1); } int m=ConvexHull(p,n,ch); double S=0; for(int i=2;i<m;i++){ Point A,B; A=Point(ch[i].x-ch[1].x,ch[i].y-ch[1].y); B=Point(ch[i+1].x-ch[1].x,ch[i+1].y-ch[1].y); S+=0.5*Cross(A,B); } //printf("%.2f\n",S); printf("%d\n",(int)S/50); } }