首先求多边形面积,这个比较简单,用的就是把一个多边形划分为多个三角形,然后求三角形面积。
代码:
double Cross(Vector A,Vector B) { return (A.x*B.y-A.y*B.x); } double ConvexPolygonArea(Point* p,int n)//多边形面积,,点按顺序 { double area=0; for(int i=1;i<n-1;i++) area+=Cross(p[i]-p[0],p[i+1]-p[0]); return area/2; }
求凸包的算法有很多,这里给出Andrew算法。
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <cmath> #include <queue> #include <vector> #include <map> #include <set> #include <string> using namespace std; #define Del(a,b) memset(a,b,sizeof(a)) const int N = 1010; const double esp = 1e-10; struct Point { double x,y; Point(double x=0,double y=0):x(x),y(y) {} }; typedef Point Vector; Vector operator + (Vector A,Vector B) { return Vector(A.x+B.x,A.y+B.y); } Vector operator - (Vector A,Vector B) { return Vector(A.x-B.x,A.y-B.y); } Vector operator * (Vector A,double p) { return Vector(A.x*p,A.y*p); } Vector operator / (Vector A,double p) { return Vector(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)<esp) return 0; else return x<0?-1:1; } bool operator == (const Point& a,const Point& b) { return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y)==0; } ///计算点积,及向量长度,及向量夹角 double Dot(Vector A,Vector B) { return A.x*B.x+A.y*B.y; } double Length(Vector A) { return sqrt(Dot(A,A)); } double Angle(Vector A,Vector B) { return acos(Dot(A,B))/Length(A)/Length(B); } //计算叉积,向量逆时针旋转 double Cross(Vector A,Vector B) { return (A.x*B.y-A.y*B.x); } double Area2(Vector A,Vector B,Vector C) { return Cross(B-A,C-A); } Vector Rotate(Vector A,double rad) { return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad)); } int cmp(Point a,Point b) { if(a.x!=b.x) return a.x<b.x; if(a.y!=b.y) return a.y<b.y; } double ConvexPolygonArea(Point* p,int n)//多边形面积,,点按顺序 { double area=0; for(int i=1;i<n-1;i++) area+=Cross(p[i]-p[0],p[i+1]-p[0]); return area/2; } int ConvexHull(Point *p,Point *ch,int n)//求凸包 { sort(p,p+n); int i,m=0,k; for(i=0;i<n;i++) { while(m>1&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--; ch[m++]=p[i]; } k=m; for(i=n-2;i>=0;i--) { while(m>k&&Cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0)m--; ch[m++]=p[i]; } if(n>1)m--; return m; } int main() { int n,k; Point a[N],ch[N]; while(~scanf("%d",&n)) { for(int i=0;i<n;i++) scanf("%lf%lf",&a[i].x,&a[i].y); int num=ConvexHull(a,ch,n); double ans=ConvexPolygonArea(ch,num); ans/=50.0; printf("%d\n",(int)ans); } return 0; }