求凸包面积。
三角形面积等于叉积的一半~
View Code
1 /* 2 Coder:Zhaofa Fang 3 Lang:C++ 4 */ 5 #include <cstdio> 6 #include <cstdlib> 7 #include <iostream> 8 #include <cmath> 9 #include <cstring> 10 #include <algorithm> 11 #include <string> 12 #include <vector> 13 #include <queue> 14 #include <stack> 15 #include <map> 16 #include <set> 17 #define pb push_back 18 using namespace std; 19 20 //========================================== 21 const double PI=acos(-1); 22 23 struct Point 24 { 25 double x,y; 26 }point[10005],res[10005]; 27 28 double det(double x1,double y1,double x2,double y2) 29 { 30 return x1*y2-x2*y1; 31 } 32 double xmult(Point o,Point a ,Point b) 33 { 34 return det(a.x-o.x,a.y-o.y,b.x-o.x,b.y-o.y); 35 } 36 double dis(Point a,Point b) 37 { 38 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); 39 } 40 bool cmp(const Point &x,const Point &y) 41 { 42 if(xmult(point[0],x,y)==0) 43 return dis(point[0],x)<dis(point[0],y); 44 return xmult(point[0],x,y)>0; 45 } 46 double Graham(int n) 47 { 48 Point tmp; 49 int k=0,top=2; 50 for(int i=1;i<n;i++) 51 { 52 if(point[i].y<point[k].y || point[i].y==point[k].y && point[i].x<point[k].x) 53 k=i; 54 } 55 tmp=point[0],point[0]=point[k],point[k]=tmp; 56 sort(point+1,point+n,cmp); 57 res[0]=point[0],res[1]=point[1],res[2]=point[2]; 58 for(int i=3;i<n;i++) 59 { 60 while(top && xmult(res[top-1],res[top],point[i])<=0)top--; 61 res[++top]=point[i]; 62 } 63 double sum=0; 64 for(int i=2;i<top+1;i++) 65 { 66 sum += xmult(res[0],res[i-1],res[i]); 67 } 68 return sum; 69 } 70 int main() 71 { 72 int n; 73 while(~scanf("%d",&n)) 74 { 75 for(int i=0;i<n;i++) 76 { 77 scanf("%lf%lf",&point[i].x,&point[i].y); 78 } 79 printf("%d\n",(int)(Graham(n)/100)); 80 } 81 return 0; 82 }