-
Notifications
You must be signed in to change notification settings - Fork 154
/
2195 - Convex Hull.cpp
71 lines (65 loc) · 1.65 KB
/
2195 - Convex Hull.cpp
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
/*
Problem Name: Convex Hull
Problem Link: https://cses.fi/problemset/task/2195
Author: Sachin Srivastava (mrsac7)
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define P complex<int>
#define X real()
#define Y imag()
int cross(P &a, P &b, P &c) {
P u = c - b;
P v = a - b;
int cp = (conj(u) * v).Y;
return (cp > 0) - (cp < 0);
}
vector<P> hull(vector<P> &v) {
vector<P> ans = {v[0]};
for (int i = 1; i < v.size(); i++) {
while (ans.size() > 1) {
P b = ans.back();
ans.pop_back();
P a = ans.back();
P c = v[i];
if (cross(a, b, c) != 1) {
ans.push_back(b);
break;
}
}
ans.push_back(v[i]);
}
return ans;
}
signed main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#ifdef LOCAL
freopen("input.txt", "r" , stdin);
freopen("output.txt", "w", stdout);
#endif
int n; cin >> n;
vector<P> v(n);
for (int i = 0; i < n; i++) {
int x, y; cin >> x >> y;
v[i] = {x, y};
}
sort(v.begin(), v.end(),
[] (const P &a, const P &b) {
return (a.X == b.X) ? (a.Y < b.Y) : (a.X < b.X);
});
vector<P> v1 = hull(v);
sort(v.begin(), v.end(),
[] (const P &a, const P &b) {
return (a.X == b.X) ? (a.Y > b.Y) : (a.X > b.X);
});
vector<P> v2 = hull(v);
for (int i = 1; i < v2.size(); i++) {
if (v2[i] == v1[0]) break;
v1.push_back(v2[i]);
}
cout << v1.size() << endl;
for (auto i: v1)
cout << i.X << " " << i.Y << endl;
}