Cows POJ

Cows

题意：给你一些树的坐标，让你来建筑面积最大的牛场，问能养多少头牛，一个牛的面积50

思路：求凸包面积即可，先求出凸包，然后再求ch[]里面的凸包顶点集所围成的多边形的面积即可

 1 // 
 2 // Created by HJYL on 2020/2/3.
 3 //
 4 #include<iostream>
 5 #include<cstring>
 6 #include<cstdio>
 7 #include<cmath>
 8 #include<algorithm>
 9 using namespace std;
10 const double eps=1e-8;
11 const int maxn=1e5+10;
12 const int INF=0x3ffff;
13 struct Point{
14     double x,y;
15     Point(double x=0,double y=0):x(x),y(y){}
16     Point operator - (Point const &b)const
17     {
18         return Point(x-b.x ,y-b.y);
19     }
20     bool operator < (Point const &c)const{
21         if(x==c.x)
22             return y<c.y;
23         return x<c.x;
24     }
25 }p[maxn],ch[maxn];
26 int n,m;
27 double Cross(Point A,Point B)
28 {
29     return (A.x*B.y)-(A.y*B.x);
30 }
31 double PolygonArea(Point* p, int n){//p为端点集合，n为端点个数
32     double s = 0;
33     for(int i = 1; i < n-1; ++i)
34         s += Cross(p[i]-p[0], p[i+1]-p[0]);
35     return s;
36 }
37 void ConvexHull() ///**求凸包*/
38 {
39     sort(p,p+n);//n顶点数
40     m = 0;
41     for(int i = 0; i < n; i++)
42     {
43         while(m > 1 && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--;
44         ch[m++] = p[i];
45     }
46     int k = m;
47     for(int i = n-2; i >= 0; i--)
48     {
49         while(m > k && Cross(ch[m-1]-ch[m-2], p[i]-ch[m-2]) <= 0) m--;
50         ch[m++] = p[i];
51     }
52     if(n > 1) m--;
53 }
54 int main()
55 {
56     while(~scanf("%d",&n))
57     {
58         for(int i=0;i<n;i++)
59             scanf("%lf%lf",&p[i].x,&p[i].y);
60         ConvexHull();
61         double ss=PolygonArea(ch,m)/2.0;
62         int num=ss/50.0;
63         printf("%d
",num);
64     }
65     return 0;
66 }