Wall

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <string>
 4 #include <cmath>
 5 #include <sstream>
 6 #include <queue>
 7 #include <stack>
 8 #include <vector>
 9 #include <set>
10 #include <map>
11 #include <algorithm>
12 #include <functional>
13 using namespace std;
14 const int maxn = 1010;
15 const double pi=acos(-1.0);
16 
17 struct Point{
18     double x,y;
19     bool extreme;
20     int succ;
21 }P[maxn];
22 int ltl;
23 double ans;
24 
25 bool cmp(const Point p1, const Point p2){
26     if( p1.y==p2.y ) return p1.x<p2.x;
27     else return p1.y<p2.y;
28 }
29 
30 bool Toleft(Point p, Point q, Point s){
31     int area2 = p.x*q.y - p.y*q.x
32                 + q.x*s.y - q.y*s.x
33                 + s.x*p.y - s.y*p.x;
34     return area2>0;///左侧为真
35 }
36 
37 int LTL(Point P[], int n){
38     int ltl=0;
39     for(int k=1;k<n;k++){
40         if( P[k].y<P[ltl].y || (P[k].y==P[ltl].y && P[k].x<P[ltl].x)){
41             ltl=k;
42         }
43     }
44     return ltl;
45 }
46 
47 double dis(int i,int j){
48     double xx=P[i].x-P[j].x;
49     double yy=P[i].y-P[j].y;
50     return sqrt(xx*xx+yy*yy);
51 }
52 
53 void Jarvis(Point P[], int n){
54     for(int k=0;k<n; k++){
55         P[k].extreme = false;
56     }
57     ltl=LTL(P,n);
58     int k=ltl;
59     do{
60         P[k].extreme=true;
61         int s=-1;
62         for(int t=0;t<n;t++){
63             if( t!=k && t!=s && (s==-1 || Toleft(P[k],P[s],P[t]))){
64                 s=t;
65             }
66         }
67         P[k].succ = s;
68         ans += dis(k,P[k].succ);
69         k=s;
70     }while(ltl!=k);
71 }
72 
73 int main()
74 {
75     int n;
76     double r;
77     scanf("%d%lf",&n,&r);
78     for(int i=0;i<n;i++){
79         scanf("%lf%lf",&P[i].x,&P[i].y);
80     }
81     ans = 0.0;
82     sort(P,P+n,cmp);///一定要排序
83     Jarvis(P,n);
84 //    int k=ltl;
85 //    do{
86 //        ans += dis(k,P[k].succ);
87 //        k = P[k].succ;
88 //    }while(k!=ltl);
89 
90     ans += 2*pi*r;
91     printf("%.0f\n",ans);
92     return 0;
93 }