From 5ab8a5088b729a9953b8dff1b2a985dc8fb2098b Mon Sep 17 00:00:00 2001 From: mzuenni Date: Mon, 27 Jun 2022 17:19:28 +0200 Subject: updated tcr --- geometry/convexHull.cpp | 39 +++++++++++++++++---------------------- 1 file changed, 17 insertions(+), 22 deletions(-) (limited to 'geometry/convexHull.cpp') diff --git a/geometry/convexHull.cpp b/geometry/convexHull.cpp index 9c14c45..e988977 100644 --- a/geometry/convexHull.cpp +++ b/geometry/convexHull.cpp @@ -1,24 +1,19 @@ -// Laufzeit: O(n*log(n)) -ll cross(const pt p, const pt a, const pt b) { - return (a.x - p.x) * (b.y - p.y) - (a.y - p.y) * (b.x - p.x); -} - -// Punkte auf der konvexen Hülle, gegen den Uhrzeigersinn sortiert. -// Kollineare Punkte nicht enthalten, entferne dafür "=" im CCW-Test. -// Achtung: Der erste und letzte Punkt im Ergebnis sind gleich. -// Achtung: Alle Punkte müssen verschieden sein. vector convexHull(vector p){ - int n = p.size(), k = 0; - vector h(2 * n); - sort(p.begin(), p.end()); - for (int i = 0; i < n; i++) { // Untere Hülle. - while (k >= 2 && cross(h[k - 2], h[k - 1], p[i]) <= 0.0) k--; - h[k++] = p[i]; - } - for (int i = n - 2, t = k + 1; i >= 0; i--) { // Obere Hülle. - while (k >= t && cross(h[k - 2], h[k - 1], p[i]) <= 0.0) k--; - h[k++] = p[i]; - } - h.resize(k); - return h; + sort(p.begin(), p.end(), [](const pt& a, const pt& b){ + return real(a) == real(b) ? imag(a) < imag(b) + : real(a) < real(b); + }); + p.erase(unique(p.begin(), p.end()), p.end()); + int k = 0; + vector h(2 * sz(p)); + for (int i = 0; i < sz(p); i++) {// Untere Hülle. + while (k > 1 && cross(h[k-2], h[k-1], p[i]) <= 0) k--; + h[k++] = p[i]; + } + for (int i = sz(p)-2, t = k; i >= 0; i--) {// Obere Hülle. + while (k > t && cross(h[k-2], h[k-1], p[i]) <= 0) k--; + h[k++] = p[i]; + } + h.resize(k); + return h; } -- cgit v1.2.3