【poj 3348】求凸包面积

题目链接：https://vjudge.net/problem/POJ-3348

直接求凸包，然后用叉积求三角形面积。最后要除2，然后因为答案要除50，所以最后除100.

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<algorithm>
 5 using namespace std;
 6 const int N=1e4+9;
 7 struct Point{
 8     int x,y;
 9     Point operator - (const Point& b)const{
10         return (Point){x-b.x,y-b.y};
11     }
12     int operator ^ (const Point& b)const{
13         return x*b.y-b.x*y;
14     }
15 }a[N],p0;
16 int n;
17 int sta[N];
18 bool cmp(Point u,Point v){
19     if(atan2(u.y-p0.y,u.x-p0.x) != atan2(v.y-p0.y,v.x-p0.x)){
20         return atan2(u.y-p0.y,u.x-p0.x) < atan2(v.y-p0.y,v.x-p0.x);
21     }
22     return u.x<v.x;
23 }
24 void init(){
25     int k;
26     scanf("%d %d",&a[0].x,&a[0].y);
27     p0=a[0];
28     for(int i=1;i<n;++i){
29         scanf("%d %d",&a[i].x,&a[i].y);
30         if(p0.y > a[i].y ||(p0.y==a[i].y && p0.x > a[i].x)){
31             p0=a[i];
32             k=i;
33         }
34     }
35     a[k]=a[0];
36     a[0]=p0;
37     sort(a+1,a+n,cmp);
38 }
39 void graham(){
40     if(n<=2){
41         printf("0");
42         return;
43     }
44     sta[0]=0; sta[1]=1;
45     int top=1;
46     for(int i=2;i<n;++i){
47         while(top > 0 && ((a[i]-a[sta[top-1]]) ^ (a[sta[top]]-a[sta[top-1]])) >= 0 ) --top;
48         sta[++top]=i;
49     }
50     int ans=0;
51     for(int i=1;i<top;++i){
52         ans+=((a[sta[i]]-p0) ^ (a[sta[i+1]]-p0) );
53     }
54     printf("%d",ans/100);
55 }
56 int main(){
57     scanf("%d",&n);
58     init();
59     graham();
60 }

View Code