-
Notifications
You must be signed in to change notification settings - Fork 2
/
convex_hull.cpp
67 lines (61 loc) · 1.63 KB
/
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
#include <bits/stdc++.h>
#define endl '\n'
#define eat cin
#define moo cout
#define int long long
using namespace std;
int cross(pair<int, int> u, pair<int, int> v){
return u.first * v.second - u.second * v.first;
}
int ccw(pair<int, int> a, pair<int, int> b, pair<int, int> c){
return cross({b.first-a.first, b.second-a.second}, {c.first-b.first, c.second-b.second});
}
int N;
pair<int, int> P[200000];
vector<pair<int, int>> convex_hull(){
vector<pair<int, int>> ans;
for(int i = 0; i < N; i++){
while(ans.size() > 1){
if(ccw(ans[ans.size()-2], ans[ans.size()-1], P[i]) >= 0) break;
ans.pop_back();
}
ans.push_back(P[i]);
}
return ans;
}
int32_t main(){
eat.tie(0) -> sync_with_stdio(0);
eat >> N;
for(int i = 0; i < N; i++){
eat >> P[i].first >> P[i].second;
}
pair<int, int> piv = {1e18, 1e18};
for(int i = 0; i < N; i++){
if(P[i].first < piv.first){
piv = P[i];
}
}
sort(P, P+N, [&](pair<int, int> a, pair<int, int> b){
if(a == piv) return true;
if(b == piv) return false;
int z = ccw(piv, a, b);
return (z == 0 ? a > b : z > 0);
});
vector<pair<int, int>> ansCCW = convex_hull();
sort(P, P+N, [&](pair<int, int> a, pair<int, int> b){
if(a == piv) return true;
if(b == piv) return false;
int z = ccw(piv, a, b);
return (z == 0 ? a < b : z > 0);
});
vector<pair<int, int>> ansCW = convex_hull();
vector<pair<int, int>> ans;
for(auto i : ansCCW) ans.push_back(i);
for(auto i : ansCW) ans.push_back(i);
sort(ans.begin(), ans.end());
int sz = unique(ans.begin(), ans.end()) - ans.begin();
moo << sz << endl;
for(int i = 0; i < sz; i++){
moo << ans[i].first << ' ' << ans[i].second << endl;
}
}