summaryrefslogtreecommitdiff
path: root/content/geometry
diff options
context:
space:
mode:
Diffstat (limited to 'content/geometry')
-rw-r--r--content/geometry/antipodalPoints.cpp8
-rw-r--r--content/geometry/closestPair.cpp15
-rw-r--r--content/geometry/convexHull.cpp22
-rw-r--r--content/geometry/delaunay.cpp12
-rw-r--r--content/geometry/geometry.tex1
-rw-r--r--content/geometry/linesAndSegments.cpp4
-rw-r--r--content/geometry/polygon.cpp26
-rw-r--r--content/geometry/segmentIntersection.cpp4
-rw-r--r--content/geometry/sortAround.cpp2
9 files changed, 42 insertions, 52 deletions
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<pair<int, int>> antipodalPoints(vector<pt>& h) {
- if (sz(h) < 2) return {};
+ if (ssize(h) < 2) return {};
vector<pair<int, int>> 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<pt>::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<pt>::iterator a, int l, int r) {
return ans;
}
-ll shortestDist(vector<pt> 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<pt> 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<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;
}
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<QuadEdge*, QuadEdge*> rec(IT l, IT r) {
}
vector<pt> delaunay(vector<pt> 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<QuadEdge*> edges = {r};
while (cross(r->onext->dest(), r->dest(), r->orig) < 0) r = r->onext;
auto add = [&](QuadEdge* e){
@@ -118,7 +116,7 @@ vector<pt> delaunay(vector<pt> 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<pt>& 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<pt>& 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<pt>& poly) { //poly[0] == poly.back()
// selbstschneidenden Polygonen (definitions Sache)
ll windingNumber(pt p, const vector<pt>& 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<pt>& poly) {
// Ändere Zeile 32 falls rand zählt, poly[0] == poly.back()
bool inside(pt p, const vector<pt>& 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<pt>& poly) {
// convex hull without duplicates, h[0] != h.back()
// apply comments if border counts as inside
bool insideConvex(pt p, const vector<pt>& 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<pt>& hull) {
}
void rotateMin(vector<pt>& 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<pt> minkowski(vector<pt> ps, vector<pt> qs) {
ps.push_back(ps[1]);
qs.push_back(qs[1]);
vector<pt> 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<pt>& ps, vector<pt> 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<pt>& 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<pt>& 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<int> intersectLine(const vector<pt>& 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<int> 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<int, int> intersect(vector<seg>& 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<seg> q;
- vector<set<seg>::iterator> where(sz(segs));
+ vector<set<seg>::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<pt>& 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;
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 19:05:50 +0000