HDU 1392

凸包模板题
 1 #include <cstdio>
 2 #include <iostream>
 3 #include <algorithm>
 4 #include <cmath>
 5 using namespace std;
 6 int n,top;
 7 struct point{
 8     double x,y;
 9 }tree[105],sta[105];
10 double dis(point a,point b){
11     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
12 }
13 double multiply(point a,point b,point c){
14     return (b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);
15 }
16 bool cmp(point a,point b){
17     return a.x==b.x?a.y<b.y:a.x<b.y;
18 }
19 int cmp ( const void *p1 , const void *p2 )
20 {
21     point *p3,*p4;
22     double m;
23     p3 = (point *)p1;
24     p4 = (point *)p2;
25     m = multiply(tree[0] , *p3 , *p4) ;
26     if(m < 0) return 1;
27     else if(m == 0 && (dis(tree[0] , *p3) < dis(tree[0],*p4)))
28         return 1;
29     else return -1;
30 }
31 void Graham(){
32     int i ;
33     sta[0].x = tree[0].x;
34     sta[0].y = tree[0].y;
35     sta[1].x = tree[1].x;
36     sta[1].y = tree[1].y;
37     sta[2].x = tree[2].x;
38     sta[2].y = tree[2].y;
39     top = 2;
40     for ( i = 3 ; i <= n ; ++ i )
41     {
42         while (multiply(sta[top - 1] , sta[top] , tree[i]) <= 0 )
43             top -- ;                          //出栈
44         sta[top + 1].x = tree[i].x ;
45         sta[top + 1].y = tree[i].y ;
46         top ++ ;
47     }
48 }
49 int main(){
50     int pos;
51     double temp,px,py;
52     while(scanf("%d",&n)&&n){
53         for(int i=0;i<n;i++){
54             scanf("%lf%lf",&tree[i].x,&tree[i].y);
55         }
56         if(n==1){printf("0.00
");continue;}
57         else if(n==2){printf("%.2lf
",dis(tree[0],tree[1]));continue;}
58         px=tree[0].x,py=tree[0].y,pos=0;
59         for(int i=1;i<n;i++){
60             if(tree[i].x<px){
61                 px=tree[i].x;
62                 py=tree[i].y;
63                 pos=i;
64             }
65             else if(tree[i].x==px&&tree[i].y<py){
66                 px=tree[i].x;
67                 py=tree[i].y;
68                 pos=i;
69             }
70         }
71         temp = tree[0].x ;                      // 找出左下角的点
72         tree[0].x = tree[pos].x ;
73         tree[pos].x = temp ;
74         temp = tree[0].y ;
75         tree[0].y = tree[pos].y ;
76         tree[pos].y = temp ;
77         qsort(&tree[1],n - 1,sizeof(double) * 2,cmp);
78         //for(int i=0;i<n;i++)printf("%lf %lf
",tree[i].x,tree[i].y);
79         tree[n].x=tree[0].x,tree[n].y=tree[0].y;
80         Graham();
81         double len = 0.0;
82         for(int i = 0 ; i < top ; i ++)
83             len = len + dis(sta[i] , sta[i+1]) ;
84         printf("%.2lf
",len);
85     }
86     return 0;
87 }