374

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
struct pt {
double x, y;
pt() {}
pt(double _x, double _y) : x(_y), y(_y) {}
pt operator-(const pt &p) const {
return pt(x-p.x, y-p.y);
}
double len() {
return sqrt(x*x+y*y);
}
};
inline double cross(const pt &p1, const pt &p2) {
return p1.x*p2.y-p1.y*p2.x;
}
const double eps = 1e-6;
int n;
vector<pt> stack;
vector<pt> pts;
pt p0;
bool debug(double a) {
cout <<"Debug: " <<fixed <<setprecision(3) <<a <<endl;
return true;
}
bool cmp(pt& a, pt& b)
{
pt p1 = a - p0;
pt p2 = b - p0;
return (p1.x*p2.y - p2.x*p1.y > eps) || ( (fabs(p1.x*p2.y - p2.x*p1.y) < eps) && (p1.len() < p2.len()) );
}
double build() {
int imostLeft = 0;
for(int i = 1; i < n; i++) {
if((pts[i].x < pts[imostLeft].x) || ((pts[i].x == pts[imostLeft].x) && (pts[i].y < pts[imostLeft].y))) {
imostLeft = i;
}
}
p0 = pts[imostLeft];
pts.erase(pts.begin() + imostLeft), n--, stack.pb(p0);
sort(all(pts), cmp); //[&](pt &p1, pt &p2) { return (abs((p1.y-p0.y)*(p2.x-p0.x) - (p1.x-p0.x)*(p2.y-p0.y)) > eps) ? ((p1.y-p0.y)*(p2.x-p0.x) < (p1.x-p0.x)*(p2.y-p0.y)) : ((p1-p0).len() < (p2-p0).len()); });
//debug(abs((pts[1].y-p0.y)*(pts[2].x-p0.x) - (pts[1].x-p0.x)*(pts[2].y-p0.y)));
stack.pb(pts[0]);
for(int i = 1; i < n; i++) {
pt pcur = pts[i];
while(stack.size() > 1) {
pt ptop = stack.back();
pt prev = *(stack.end() - 2);
if(cross(pcur-ptop, prev-ptop) > eps) {
break;
}
stack.erase(stack.end() - 1);
}
stack.pb(pcur);
}
n = (int)stack.size();
double ans = 0;
for(int i = 0; i < n; i++) {
ans += (stack[i]-stack[(i+1)%n]).len();
}
return ans;
}
int main() {
//freopen
cin >>n;
pts.resize(n);
for(int i = 0; i < n; i++) {
cin >>pts[i].x >>pts[i].y;
}
double ans = build();
cout <<fixed <<setprecision(6) <<ans <<endl;
return 0;
}