aboutsummaryrefslogtreecommitdiff
path: root/Geometry
diff options
context:
space:
mode:
authorAnthony Wang2020-06-04 17:59:54 -0500
committerGitHub2020-06-04 17:59:54 -0500
commit13248161558849612b860548927dbe411ccf54f5 (patch)
tree3495615743378d9fc8ef00a72f95667c5987ebd0 /Geometry
parent33c29a0aafd3ebfe0335d7f104cfd4584031f63d (diff)
Update polygons.cpp
Diffstat (limited to 'Geometry')
-rw-r--r--Geometry/polygons.cpp59
1 files changed, 21 insertions, 38 deletions
diff --git a/Geometry/polygons.cpp b/Geometry/polygons.cpp
index 2dcdefd..12359d9 100644
--- a/Geometry/polygons.cpp
+++ b/Geometry/polygons.cpp
@@ -1,63 +1,46 @@
struct point {
- int x, y;
+ ll x, y; // long long to avoid overflow problems
point() { x = y = 0; }
- point(int _x, int _y) : x(_x), y(_y) {}
- bool operator < (point p) const {
- return (x == p.x && y < p.y) || x < p.x;
- }
- bool operator == (point p) const {
- return x == p.x && y == p.y;
- }
+ point(ll _x, ll _y) : x(_x), y(_y) {}
+ bool operator < (point p) const { return (x == p.x && y < p.y) || x < p.x; }
+ bool operator == (point p) const { return x == p.x && y == p.y; }
};
-double dist(point& p1, point& p2) {
- return hypot(p1.x - p2.x, p1.y - p2.y);
-}
+double dist(point& p1, point& p2) { return hypot(p1.x - p2.x, p1.y - p2.y); }
struct vec {
- int x, y;
- vec(int _x, int _y) : x(_x), y(_y) {}
+ ll x, y;
+ vec(ll _x, ll _y) : x(_x), y(_y) {}
+ vec(point a, point b) { x = b.x - a.x, y = b.y - a.y; }
};
-vec to_vec(point a, point b) {
- return vec(b.x - a.x, b.y - a.y);
-}
+ll dot(vec a, vec b) { return a.x * b.x + a.y * b.y; }
-int dot(vec a, vec b) {
- return (a.x * b.x + a.y * b.y);
-}
+ll norm_sq(vec v) { return v.x * v.x + v.y * v.y; }
-int norm_sq(vec v) {
- return v.x * v.x + v.y * v.y;
-}
-
-int cross(vec a, vec b) {
- return a.x * b.y - a.y * b.x;
-}
-
-bool ccw(point p, point q, point r) {
- return cross(to_vec(p, q), to_vec(p, r)) > 0;
-}
+ll cross(vec a, vec b) { return a.x * b.y - a.y * b.x; }
double angle(point a, point o, point b) {
- vec oa = to_vec(o, a), ob = to_vec(o, b);
- return acos(dot(oa, ob) / (sqrt(norm_sq(oa)) * sqrt(norm_sq(ob))));
+ vec oa(o, a), ob(o, b);
+ return acos(dot(oa, ob) / sqrt(norm_sq(oa) * norm_sq(ob)));
}
+bool ccw(point p, point q, point r) { return cross(vec(p, q), vec(p, r)) > 0; }
+
bool in_polygon(point pt, const vector<point>& P) {
double sum = 0;
for (int i = 0; i < P.size() - 1; i++) {
if (pt == P[i]) return true;
- if (ccw(pt, P[i], P[i + 1])) sum += angle(P[i], pt, P[i + 1]);
- else sum -= angle(P[i], pt, P[i + 1]);
+ ccw(pt, P[i], P[i + 1]) ? sum += angle(P[i], pt, P[i + 1]) : sum -= angle(P[i], pt, P[i + 1]);
}
return fabs(sum) > acos(-1.0);
}
-double area(const vector<point>& P) {
- int res = 0;
- for (int i = 0; i < (int)P.size() - 1; i++) res += (P[i].x * P[i + 1].y - P[i + 1].x * P[i].y);
- return res / 2.0;
+ll area(const vector<point>& P) {
+ ll res = 0;
+ for (int i = 0; i < (int)P.size() - 1; i++) res += (P[i].x * P[i + 1].y - P[i + 1].x * P[i].y);
+ return res;
+ // return res / 2.0;
}
vector<point> convex_hull(vector<point>& P) {