-
Notifications
You must be signed in to change notification settings - Fork 21
/
geometry.hpp
74 lines (65 loc) · 2.36 KB
/
geometry.hpp
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
// type of coordinates
typedef double pType;
struct Point {
pType x,y;
Point() {}
Point(pType x,pType y):x(x),y(y) {}
// use brackets with all operators e.g use (a ^ b) instead of just a ^ b
// vector addition
Point operator +(const Point &rhs) const { return Point(this->x + rhs.x, this->y + rhs.y); }
// vector subtraction
Point operator -(const Point &rhs) const { return Point(this->x - rhs.x, this->y - rhs.y); }
bool operator ==(const Point &rhs) const { return (this->x == rhs.x && this->y == rhs.y);}
bool operator <(const Point &rhs) const { if(this->x != rhs.x) return this->x < rhs.x; return this->y < rhs.y;}
// cross product
pType operator ^(const Point &rhs) const { return this->x * rhs.y - this->y * rhs.x; }
// dot product
pType operator *(const Point &rhs) const { return this->x * rhs.x + this->y * rhs.y; }
void print() {
cout << "[" << x << " , " << y << "]";
}
};
// scalar multiplication
Point operator *(pType c, const Point &p) { return Point(c * p.x, c * p.y); }
// square of length
pType len2(const Point & p) { return p * p; }
// square of distance between two vectors
pType dis2(const Point & p, const Point & q) { return len2(p - q); }
// convex hull (monotone chain) O(nlogn)
// pass a vector of unique points
vector <Point> convexHull(vector <Point> pts) {
vector <Point> hull;
sort(pts.begin(), pts.end());
int n = (int)pts.size();
hull.push_back(pts[0]);
int nh = 1, start = 0;
for(int i = 0; i < n; ++i) {
Point p = pts[i];
while(nh - start >= 2 and ((p - hull[nh - 1]) ^ (hull[nh - 1] - hull[nh - 2])) >= 0) {
hull.pop_back(); --nh;
}
hull.push_back(p); ++nh;
}
start = nh - 1;
for(int i = n - 2; i >= 0; --i) {
Point p = pts[i];
while(nh - start >= 2 and ((p - hull[nh - 1]) ^ (hull[nh - 1] - hull[nh - 2])) >= 0) {
hull.pop_back(); --nh;
}
hull.push_back(p); ++nh;
}
hull.pop_back();
return hull;
}
// area of a convex hull of a vector of points
double area(vector <Point> & pts) {
sort(all(pts));
pts.erase(unique(all(pts)), pts.end());
if(sz(pts) <= 2) return 0.0;
double ar = 0.0;
vector <Point> hull = convexHull(pts);
rep(i, sz(hull)) {
ar += hull[i] ^ hull[(i + 1) % sz(hull)];
}
return 0.5 * ar;
}