hdu 1392 Surround the Trees

题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=1392

题意：给出一些点的坐标，求最小的凸多边形把所有点包围时此多边形的周长。

解法：凸包ConvexHull 模板题

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<cstdlib>
 6 #include<algorithm>
 7 #define inf 0x7fffffff
 8 #define PI 3.141592654
 9 #define exp 1e-10
10 using namespace std;
11 struct Point
12 {
13     double x,y;
14     Point (double x=0,double y=0):x(x),y(y){}
15     friend bool operator < (Point A,Point B)
16     {
17         if (A.x != B.x) return A.x < B.x;
18         return A.y<B.y;
19     }
20 }an[111];
21 typedef Point Vector;
22 Vector operator + (Vector A,Vector B) {return Vector(A.x+B.x , A.y+B.y); }
23 Vector operator - (Vector A,Vector B) {return Vector(A.x-B.x , A.y-B.y); }
24 
25 int dcmp(double x)
26 {
27     if (fabs(x)<exp) return 0;
28     else return x<0 ? -1 : 1;
29 }
30 double cross(Vector A,Vector B)
31 {
32     return A.x*B.y-B.x*A.y;
33 }
34 int ConvexHull(Point *p,int n,Point *ch)
35 {
36     sort(p,p+n);
37     int m=0;
38     for (int i=0 ;i<n ;i++)
39     {
40         while (m>1 && dcmp(cross(ch[m-1]-ch[m-2] , p[i]-ch[m-2]))<=0) m--;
41         ch[m++]=p[i];
42     }
43     int k=m;
44     for (int i=n-2 ;i>=0 ;i--)
45     {
46         while (m>k && dcmp(cross(ch[m-1]-ch[m-2] , p[i]-ch[m-2]))<=0) m--;
47         ch[m++]=p[i];
48     }
49     ch[m++]=ch[0];
50     if (n>1) m--;
51     return m;
52 }
53 double dis(Point a,Point b)
54 {
55     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
56 }
57 int main()
58 {
59     int n;
60     while (cin>>n,n)
61     {
62         for (int i=0 ;i<n ;i++)
63         scanf("%lf%lf",&an[i].x,&an[i].y);
64         if (n==1) {printf("0.00
");continue;}
65         else if (n==2) {printf("%.2f
",dis(an[0],an[1]));continue;}
66         Point bn[111];
67         int m=ConvexHull(an,n,bn);
68         double sum=0;
69         for (int i=0 ;i<m ;i++)
70         {
71             sum += dis(bn[i],bn[i+1]);
72         }
73         printf("%.2f
",sum);
74     }
75     return 0;
76 }