summaryrefslogtreecommitdiff
path: root/geometry/convexHull.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'geometry/convexHull.cpp')
-rw-r--r--geometry/convexHull.cpp19
1 files changed, 0 insertions, 19 deletions
diff --git a/geometry/convexHull.cpp b/geometry/convexHull.cpp
deleted file mode 100644
index b1de170..0000000
--- a/geometry/convexHull.cpp
+++ /dev/null
@@ -1,19 +0,0 @@
-vector<pt> convexHull(vector<pt> pts){
- sort(all(pts), [](const pt& a, const pt& b){
- return real(a) == real(b) ? imag(a) < imag(b)
- : real(a) < real(b);
- });
- pts.erase(unique(all(pts)), pts.end());
- int k = 0;
- vector<pt> h(2 * sz(pts));
- for (int i = 0; i < sz(pts); i++) {// Untere Hülle.
- while (k > 1 && cross(h[k-2], h[k-1], pts[i]) <= 0) k--;
- h[k++] = pts[i];
- }
- for (int i = sz(pts)-2, t = k; i >= 0; i--) {// Obere Hülle.
- while (k > t && cross(h[k-2], h[k-1], pts[i]) <= 0) k--;
- h[k++] = pts[i];
- }
- h.resize(k);
- return h;
-}