首页 > 代码库 > POJ 3348 最直接的凸包问题

POJ 3348 最直接的凸包问题

题目大意:

给定一堆树的点,找到能组合成的最大面积,一个物体占50面积,求最多放多少物体

 

 1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 using namespace std; 6 const double eps = 1e-10; 7 const int N = 10005; 8 double myabs(double x) 9 {10     return x>0?x:-x;11 }12 struct Point{13     double x,y;14     Point(double x=0 , double y=0):x(x),y(y){}15 };16 Point p[N] , ch[N];17 typedef Point Vector;18 Vector operator+(Vector a , Vector b){19     return Vector(a.x + b.x , a.y + b.y);20 }21 Vector operator-(Point a , Point b){22     return Vector(a.x - b.x , a.y - b.y);23 }24 Vector operator*(Vector a, double b){25     return Vector(a.x*b , a.y*b);26 }27 Vector operator/(Vector a, double b){28     return Vector(a.x / b , a.y/b);29 }30 int dcmp(double x){31     if(myabs(x) < eps) return 0;32     return x<0?-1:1;33 }34 bool operator==(Point a ,Point b){35     return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0;36 }37 bool operator<( Point a , Point b){38     return dcmp(a.x-b.x)<0 || (dcmp(a.x-b.x)==0 && dcmp(a.y-b.y)<0);39 }40 double Cross(Vector a , Vector b){41     return a.x*b.y - b.x*a.y;42 }43 double get_polexy_area(Point *p , int n){44     double ans = 0;45     for(int i=1;i<n-1;i++){46         ans += Cross(p[i] - p[0] , p[i+1] - p[0]);47     }48     return ans / 2;49 }50 int ConvexHull(Point *p, int n) //凸包51 {52     sort(p, p+n);53     n = unique(p, p+n) - p; //去重54     int m = 0;55     for(int i = 0; i < n; i++)56     {57         while(m > 1 && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--;58         ch[m++] = p[i];59     }60     int k = m;61     for(int i = n-2; i >= 0; i--)62     {63         while(m > k && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--;64         ch[m++] = p[i];65     }66     if(n > 1) m--;67     return m;68 }69 int main()70 {71     //freopen("test.in","rb",stdin);72     int n;73     while(~scanf("%d",&n)){74         for(int i=0;i<n;i++){75             scanf("%lf%lf" , &p[i].x , &p[i].y);76         }77         int m = ConvexHull(p,n);78         double area = get_polexy_area(ch , m);79         int ans = (int)(area/50);80         printf("%d\n",ans);81     }82     return 0;83 }

 

POJ 3348 最直接的凸包问题