首页 > 代码库 > 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 最直接的凸包问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。