diff options
Diffstat (limited to 'geometry/convexHull.cpp')
| -rw-r--r-- | geometry/convexHull.cpp | 20 |
1 files changed, 10 insertions, 10 deletions
diff --git a/geometry/convexHull.cpp b/geometry/convexHull.cpp index e988977..9245acc 100644 --- a/geometry/convexHull.cpp +++ b/geometry/convexHull.cpp @@ -1,18 +1,18 @@ -vector<pt> convexHull(vector<pt> p){ - sort(p.begin(), p.end(), [](const pt& a, const pt& b){ +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); }); - p.erase(unique(p.begin(), p.end()), p.end()); + pts.erase(unique(all(pts)), pts.end()); int k = 0; - vector<pt> 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]; + 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(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]; + 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; |