diff options
Diffstat (limited to 'content/geometry/convexHull.cpp')
| -rw-r--r-- | content/geometry/convexHull.cpp | 22 |
1 files changed, 10 insertions, 12 deletions
diff --git a/content/geometry/convexHull.cpp b/content/geometry/convexHull.cpp index 1173924..03c6343 100644 --- a/content/geometry/convexHull.cpp +++ b/content/geometry/convexHull.cpp @@ -1,18 +1,16 @@ 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()); + ranges::sort(pts, {}, + [](pt x) { return pair{real(x), imag(x)}; }); + pts.erase(begin(ranges::unique(pts)), end(pts)); int k = 0; - vector<pt> h(2 * sz(pts)); - auto half = [&](auto begin, auto end, int t) { - for (auto it = begin; it != end; it++) { - while (k > t && cross(h[k-2], h[k-1], *it) <= 0) k--; - h[k++] = *it; + vector<pt> h(2 * ssize(pts)); + auto half = [&](auto &&v, int t) { + for (auto x: v) { + while (k > t && cross(h[k-2], h[k-1], x) <= 0) k--; + h[k++] = x; }}; - half(all(pts), 1); // Untere Hülle. - half(next(pts.rbegin()), pts.rend(), k); // Obere Hülle. + half(pts, 1); // Untere Hülle. + half(pts | views::reverse | views::drop(1), k); // Obere Hülle h.resize(k); return h; } |