From 1880ccb6d85c6eb79e724593457877bab431951c Mon Sep 17 00:00:00 2001 From: Gloria Mundi Date: Sat, 16 Nov 2024 21:17:29 +0100 Subject: get rid of all() and sz() --- content/geometry/antipodalPoints.cpp | 8 ++++---- content/geometry/closestPair.cpp | 15 ++++++--------- content/geometry/convexHull.cpp | 22 ++++++++++------------ content/geometry/delaunay.cpp | 12 +++++------- content/geometry/geometry.tex | 1 + content/geometry/linesAndSegments.cpp | 4 +--- content/geometry/polygon.cpp | 26 ++++++++++++-------------- content/geometry/segmentIntersection.cpp | 4 ++-- content/geometry/sortAround.cpp | 2 +- 9 files changed, 42 insertions(+), 52 deletions(-) (limited to 'content/geometry') diff --git a/content/geometry/antipodalPoints.cpp b/content/geometry/antipodalPoints.cpp index 110cc74..b34b175 100644 --- a/content/geometry/antipodalPoints.cpp +++ b/content/geometry/antipodalPoints.cpp @@ -1,12 +1,12 @@ vector> antipodalPoints(vector& h) { - if (sz(h) < 2) return {}; + if (ssize(h) < 2) return {}; vector> result; for (int i = 0, j = 1; i < j; i++) { while (true) { result.push_back({i, j}); - if (cross(h[(i + 1) % sz(h)] - h[i], - h[(j + 1) % sz(h)] - h[j]) <= 0) break; - j = (j + 1) % sz(h); + if (cross(h[(i + 1) % ssize(h)] - h[i], + h[(j + 1) % ssize(h)] - h[j]) <= 0) break; + j = (j + 1) % ssize(h); }} return result; } diff --git a/content/geometry/closestPair.cpp b/content/geometry/closestPair.cpp index 9b115f3..bbefa67 100644 --- a/content/geometry/closestPair.cpp +++ b/content/geometry/closestPair.cpp @@ -4,12 +4,11 @@ ll rec(vector::iterator a, int l, int r) { ll midx = a[m].real(); ll ans = min(rec(a, l, m), rec(a, m, r)); - inplace_merge(a+l, a+m, a+r, [](const pt& x, const pt& y) { - return x.imag() < y.imag(); - }); + ranges::inplace_merge(a+l, a+m, a+r, {}, + [](pt x) { return imag(x); }); pt tmp[8]; - fill(all(tmp), a[l]); + ranges::fill(tmp, a[l]); for (int i = l + 1, next = 0; i < r; i++) { if (ll x = a[i].real() - midx; x * x < ans) { for (pt& p : tmp) ans = min(ans, norm(p - a[i])); @@ -19,9 +18,7 @@ ll rec(vector::iterator a, int l, int r) { return ans; } -ll shortestDist(vector a) { // sz(pts) > 1 - sort(all(a), [](const pt& x, const pt& y) { - return x.real() < y.real(); - }); - return rec(a.begin(), 0, sz(a)); +ll shortestDist(vector a) { // size(pts) > 1 + ranges::sort(a, {}, [](pt x) { return real(x); }); + return rec(a.begin(), 0, ssize(a)); } 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 convexHull(vector 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 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 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; } diff --git a/content/geometry/delaunay.cpp b/content/geometry/delaunay.cpp index 5672b57..9ae9061 100644 --- a/content/geometry/delaunay.cpp +++ b/content/geometry/delaunay.cpp @@ -99,12 +99,10 @@ pair rec(IT l, IT r) { } vector delaunay(vector pts) { - if (sz(pts) <= 2) return {}; - sort(all(pts), [](const pt& a, const pt& b) { - if (real(a) != real(b)) return real(a) < real(b); - return imag(a) < imag(b); - }); - QuadEdge* r = rec(all(pts)).first; + if (ssize(pts) <= 2) return {}; + ranges::sort(pts, {}, + [](pt x) { return pair{real(x), imag(x)}; }); + QuadEdge* r = rec(begin(pts), end(pts)).first; vector edges = {r}; while (cross(r->onext->dest(), r->dest(), r->orig) < 0) r = r->onext; auto add = [&](QuadEdge* e){ @@ -118,7 +116,7 @@ vector delaunay(vector pts) { }; add(r); pts.clear(); - for (int i = 0; i < sz(edges); i++) { + for (int i = 0; i < ssize(edges); i++) { if (!edges[i]->used) add(edges[i]); } return pts; diff --git a/content/geometry/geometry.tex b/content/geometry/geometry.tex index 976fb4d..9290de4 100644 --- a/content/geometry/geometry.tex +++ b/content/geometry/geometry.tex @@ -18,6 +18,7 @@ \end{itemize} \sourcecode{geometry/convexHull.cpp} \end{algorithm} +\columnbreak \begin{algorithm}{Rotating calipers} \begin{methods} diff --git a/content/geometry/linesAndSegments.cpp b/content/geometry/linesAndSegments.cpp index db34179..985ee24 100644 --- a/content/geometry/linesAndSegments.cpp +++ b/content/geometry/linesAndSegments.cpp @@ -28,9 +28,7 @@ pt projectToLine(pt a, pt b, pt p) { // sortiert alle Punkte pts auf einer Linie entsprechend dir void sortLine(pt dir, vector& pts) { // (2d und 3d) - sort(all(pts), [&](pt a, pt b){ - return dot(dir, a) < dot(dir, b); - }); + ranges::sort(pts, {}, [&](pt x) { return dot(dir, x); }); } // Liegt p auf der Strecke a-b? (nutze < für inberhalb) diff --git a/content/geometry/polygon.cpp b/content/geometry/polygon.cpp index b9ecebb..626162a 100644 --- a/content/geometry/polygon.cpp +++ b/content/geometry/polygon.cpp @@ -2,7 +2,7 @@ // Punkte gegen den Uhrzeigersinn: positiv, sonst negativ. double area(const vector& poly) { //poly[0] == poly.back() ll res = 0; - for (int i = 0; i + 1 < sz(poly); i++) + for (int i = 0; i + 1 < ssize(poly); i++) res += cross(poly[i], poly[i + 1]); return 0.5 * res; } @@ -13,7 +13,7 @@ double area(const vector& poly) { //poly[0] == poly.back() // selbstschneidenden Polygonen (definitions Sache) ll windingNumber(pt p, const vector& poly) { ll res = 0; - for (int i = 0; i + 1 < sz(poly); i++) { + for (int i = 0; i + 1 < ssize(poly); i++) { pt a = poly[i], b = poly[i + 1]; if (real(a) > real(b)) swap(a, b); if (real(a) <= real(p) && real(p) < real(b) && @@ -27,7 +27,7 @@ ll windingNumber(pt p, const vector& poly) { // Ändere Zeile 32 falls rand zählt, poly[0] == poly.back() bool inside(pt p, const vector& poly) { bool in = false; - for (int i = 0; i + 1 < sz(poly); i++) { + for (int i = 0; i + 1 < ssize(poly); i++) { pt a = poly[i], b = poly[i + 1]; if (pointOnSegment(a, b, p)) return false; if (real(a) > real(b)) swap(a,b); @@ -41,7 +41,7 @@ bool inside(pt p, const vector& poly) { // convex hull without duplicates, h[0] != h.back() // apply comments if border counts as inside bool insideConvex(pt p, const vector& hull) { - int l = 0, r = sz(hull) - 1; + int l = 0, r = ssize(hull) - 1; if (cross(hull[0], hull[r], p) >= 0) return false; // > 0 while (l + 1 < r) { int m = (l + r) / 2; @@ -52,11 +52,9 @@ bool insideConvex(pt p, const vector& hull) { } void rotateMin(vector& hull) { - auto mi = min_element(all(hull), [](const pt& a, const pt& b){ - return real(a) == real(b) ? imag(a) < imag(b) - : real(a) < real(b); - }); - rotate(hull.begin(), mi, hull.end()); + auto mi = ranges::min_element(hull, {}, + [](pt a) { return pair{real(a), imag(a)}; }); + ranges::rotate(hull, mi); } // convex hulls without duplicates, h[0] != h.back() @@ -68,7 +66,7 @@ vector minkowski(vector ps, vector qs) { ps.push_back(ps[1]); qs.push_back(qs[1]); vector res; - for (ll i = 0, j = 0; i + 2 < sz(ps) || j + 2 < sz(qs);) { + for (ll i = 0, j = 0; i + 2 < ssize(ps) || j + 2 < ssize(qs);) { res.push_back(ps[i] + qs[j]); auto c = cross(ps[i + 1] - ps[i], qs[j + 1] - qs[j]); if(c >= 0) i++; @@ -84,7 +82,7 @@ double dist(const vector& ps, vector qs) { p.push_back(p[0]); double res = INF; bool intersect = true; - for (ll i = 0; i + 1 < sz(p); i++) { + for (ll i = 0; i + 1 < ssize(p); i++) { intersect &= cross(p[i], p[i+1]) >= 0; res = min(res, distToSegment(p[i], p[i+1], 0)); } @@ -99,7 +97,7 @@ bool left(pt of, pt p) { return cross(p, of) < 0 || // returns index of corner where dot(dir, corner) is maximized int extremal(const vector& hull, pt dir) { dir *= pt(0, 1); - int l = 0, r = sz(hull) - 1; + int l = 0, r = ssize(hull) - 1; while (l + 1 < r) { int m = (l + r) / 2; pt dm = hull[m+1]-hull[m]; @@ -111,7 +109,7 @@ int extremal(const vector& hull, pt dir) { if (cross(dir, dm) < 0) l = m; else r = m; }} - return r % (sz(hull) - 1); + return r % (ssize(hull) - 1); } // convex hulls without duplicates, hull[0] == hull.back() and @@ -127,7 +125,7 @@ vector intersectLine(const vector& hull, pt a, pt b) { if (cross(hull[endA], a, b) > 0 || cross(hull[endB], a, b) < 0) return {}; - int n = sz(hull) - 1; + int n = ssize(hull) - 1; vector res; for (auto _ : {0, 1}) { int l = endA, r = endB; diff --git a/content/geometry/segmentIntersection.cpp b/content/geometry/segmentIntersection.cpp index afc01b2..9fdbdb8 100644 --- a/content/geometry/segmentIntersection.cpp +++ b/content/geometry/segmentIntersection.cpp @@ -39,10 +39,10 @@ pair intersect(vector& segs) { events.push_back({s.a, s.id, 1}); events.push_back({s.b, s.id, -1}); } - sort(all(events)); + ranges::sort(events, less{}); set q; - vector::iterator> where(sz(segs)); + vector::iterator> where(ssize(segs)); for (auto e : events) { int id = e.id; if (e.type > 0) { diff --git a/content/geometry/sortAround.cpp b/content/geometry/sortAround.cpp index 9b09808..7e9d1de 100644 --- a/content/geometry/sortAround.cpp +++ b/content/geometry/sortAround.cpp @@ -3,7 +3,7 @@ bool left(pt p) { return real(p) < 0 || // counter clockwise, starting with "11:59" void sortAround(pt p, vector& ps) { - sort(all(ps), [&](const pt& a, const pt& b){ + ranges::sort(ps, [&](const pt& a, const pt& b){ if (left(a - p) != left(b - p)) return left(a - p) > left(b - p); return cross(p, a, b) > 0; -- cgit v1.2.3