1392

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<string>
 4 #include<vector>
 5 #include<map>
 6 #include<set>
 7 #include<cstring>
 8 #include<cstdio>
 9 #include<cmath>
10 #include<cstdlib>
11 #include<stack>
12 #include<iomanip>
13 #include<cctype>
14 #include<climits>
15 #include<queue>
16 using namespace std;
17 typedef long long ll;
18 typedef unsigned long long ull;
19 
20 struct P
21 {
22     int x,y;
23 };
24 
25 
26 const int maxn=50050;
27 int n,k;
28 P ps[maxn];
29 
30 bool cmp(const P& p,const P& q)
31 {
32     if(p.x!=q.x)
33         return p.x<q.x;
34     return p.y<q.y;
35 }
36 
37 int cross(P p0,P p1,P p2)
38 {
39     return (p2.x-p0.x)*(p1.y-p0.y)-(p1.x-p0.x)*(p2.y-p0.y);
40 }
41 
42 vector<P> convex_hull(P* ps,int n)
43 {
44     sort(ps,ps+n,cmp);
45     k=0;
46     vector<P> qs(n*2);
47     for(int i=0;i<n;i++){
48         while(k>1 && cross(qs[k-2],qs[k-1],ps[i])<=0)
49             k--;
50         qs[k++]=ps[i];
51     }
52     for(int i=n-2,t=k;i>=0;i--){
53         while(k>t && cross(qs[k-2],qs[k-1],ps[i])<=0)
54             k--;
55         qs[k++]=ps[i];
56     }
57     k--;
58     qs.resize(k);
59     return qs;
60 }
61 
62 double dis(P p,P q)
63 {
64     double dist=(p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y);
65     return sqrt(dist);
66 }
67 
68 
69 int main()
70 {
71     while(~scanf("%d",&n)){
72         if(n==0)
73             return 0;
74         for(int i=0;i<n;i++)
75             scanf("%d %d",&ps[i].x,&ps[i].y);
76         vector<P> qs=convex_hull(ps,n);
77         double ans=0;
78         if(k==0||k==1)
79             printf("0
");
80         else if(k==2)
81             printf("%.2lf
",dis(qs[0],qs[1]));
82         else{
83             for(int i=0;i<k-1;i++)
84                 ans+=dis(qs[i],qs[i+1]);
85             ans+=dis(qs[0],qs[k-1]);
86             printf("%.2lf
",ans);
87          }
88     }
89     return 0;
90 }
做题笔记，只是想积累看看四年之后写了AC了多少题。