-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathconvex_hull.cc
49 lines (44 loc) · 1.13 KB
/
convex_hull.cc
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
const double EPS = 1e-10;
double add(double a, double b) {
if (abs(a + b) < EPS * (abs(a) + abs(b))) return 0;
return a + b;
}
int add(int a, int b) {
return a + b;
}
template<class T>
struct P {
double x, y;
P() {}
P(double x, double y) : x(x), y(y) {}
double det(P p) {
return add(x * p.y, -y * p.x);
}
P operator - (P p) {
return P(add(x, -p.x), add(y, -p.y));
}
};
template<class T>
bool cmp_x(const P<T>& p, const P<T>& q) {
if (p.x != q.x) return p.x < q.x;
return p.y < q.y;
}
template<class T>
vector<P<T> > convex_hull(vector<P<T> > &ps) {
int n = ps.size();
sort(ALL(ps), cmp_x<T>);
int k = 0;
vector<P<T> > qs(n * 2);
REP(i, n) {
// XXX To include points ON the edges, change "<=" to "<"
while (k > 1 && (qs[k-1] - qs[k-2]).det(ps[i] - qs[k-1]) <= 0) k--;
qs[k++] = ps[i];
}
for (int i = n-2, t = k; i >= 0; i--) {
// XXX To include points ON the edges, change "<=" to "<"
while (k > t && (qs[k-1] - qs[k-2]).det(ps[i] - qs[k-1]) <= 0) k--;
qs[k++] = ps[i];
}
qs.resize(k-1);
return qs;
}