summaryrefslogtreecommitdiff
path: root/test/geometry
diff options
context:
space:
mode:
Diffstat (limited to 'test/geometry')
-rw-r--r--test/geometry/antipodalPoints.cpp8
-rw-r--r--test/geometry/circle.cpp12
-rw-r--r--test/geometry/closestPair.cpp2
-rw-r--r--test/geometry/closestPair.double.cpp2
-rw-r--r--test/geometry/convexHull.cpp4
-rw-r--r--test/geometry/delaunay.cpp37
-rw-r--r--test/geometry/formulas.cpp2
-rw-r--r--test/geometry/hpi.cpp48
-rw-r--r--test/geometry/polygon.cpp22
-rw-r--r--test/geometry/segmentIntersection.cpp2
-rw-r--r--test/geometry/sortAround.cpp6
11 files changed, 73 insertions, 72 deletions
diff --git a/test/geometry/antipodalPoints.cpp b/test/geometry/antipodalPoints.cpp
index d20dfb6..013f43c 100644
--- a/test/geometry/antipodalPoints.cpp
+++ b/test/geometry/antipodalPoints.cpp
@@ -9,7 +9,7 @@ constexpr ll EPS = 0;
#include "../geometry.h"
vector<pair<int, int>> naive(vector<pt> ps) {
- ll n = sz(ps);
+ ll n = ssize(ps);
auto test = [&](int i, int j){
if (dot(ps[j] - ps[i], ps[i - 1] - ps[i]) <= 0) return false;
if (dot(ps[j] - ps[i], ps[i + 1] - ps[i]) <= 0) return false;
@@ -34,13 +34,13 @@ void stress_test(ll range) {
auto got = antipodalPoints(ps);
for (auto& [a, b] : got) if (a > b) swap(a, b);
- sort(all(got));
+ ranges::sort(got);
auto expected = naive(ps);
for (auto& [a, b] : expected) if (a > b) swap(a, b);
for (auto x : expected) {
- auto it = lower_bound(all(got), x);
+ auto it = ranges::lower_bound(got, x);
if (it == got.end() || *it != x) cerr << "error" << FAIL;
}
queries += n;
@@ -58,7 +58,7 @@ void performance_test() {
auto got = antipodalPoints(ps);
t.stop();
- hash_t hash = sz(got);
+ hash_t hash = ssize(got);
if (t.time > 50) cerr << "too slow: " << t.time << FAIL;
cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
}
diff --git a/test/geometry/circle.cpp b/test/geometry/circle.cpp
index 3d3d27d..dc975ff 100644
--- a/test/geometry/circle.cpp
+++ b/test/geometry/circle.cpp
@@ -46,9 +46,9 @@ void test_circleIntersection(ll range) {
auto got = circleIntersection(c1, r1, c2, r2);
- if (sz(got) != expectedCount(real(c1), imag(c1), r1, real(c2), imag(c2), r2)) cerr << "error: wrong count" << FAIL;
+ if (ssize(got) != expectedCount(real(c1), imag(c1), r1, real(c2), imag(c2), r2)) cerr << "error: wrong count" << FAIL;
- for (int i = 0; i < sz(got); i++) {
+ for (int i = 0; i < ssize(got); i++) {
for (int j = 0; j < i; j++) {
if (abs(got[i] - got[j]) < 1e-6) cerr << "error: identical" << FAIL;
}
@@ -58,7 +58,7 @@ void test_circleIntersection(ll range) {
if (float_error(abs(c1 - p), r1) > 1e-6) cerr << "error: 1" << FAIL;
if (float_error(abs(c2 - p), r2) > 1e-6) cerr << "error: 2" << FAIL;
}
- queries += sz(got);
+ queries += ssize(got);
}
cerr << "tested circleIntersection: " << queries << endl;
}
@@ -91,9 +91,9 @@ void test_circleRayIntersection(ll range) {
else expected = 1;
}
- if (sz(got) != expected) cerr << "error: wrong count" << FAIL;
+ if (ssize(got) != expected) cerr << "error: wrong count" << FAIL;
- for (int i = 0; i < sz(got); i++) {
+ for (int i = 0; i < ssize(got); i++) {
for (int j = 0; j < i; j++) {
if (abs(got[i] - got[j]) < 1e-6) cerr << "error: identical" << FAIL;
}
@@ -103,7 +103,7 @@ void test_circleRayIntersection(ll range) {
if (float_error(abs(c - p), r) > 1e-6) cerr << "error: 1" << FAIL;
if (distToLine(orig, orig + dir, p) > 1e-6) cerr << "error: 2" << FAIL;
}
- queries += sz(got);
+ queries += ssize(got);
}
cerr << "tested circleIntersection: " << queries << endl;
}
diff --git a/test/geometry/closestPair.cpp b/test/geometry/closestPair.cpp
index 5959b21..4e558dc 100644
--- a/test/geometry/closestPair.cpp
+++ b/test/geometry/closestPair.cpp
@@ -13,7 +13,7 @@ ll isqrt(ll x) {return (ll)sqrtl(x);}
//strict convex hull
ll naive(const vector<pt>& ps) {
ll opt = LL::INF;
- for (ll i = 0; i < sz(ps); i++) {
+ for (ll i = 0; i < ssize(ps); i++) {
for (ll j = 0; j < i; j++) {
opt = min(opt, norm(ps[i] - ps[j]));
}
diff --git a/test/geometry/closestPair.double.cpp b/test/geometry/closestPair.double.cpp
index 2f8a1ab..9ef039f 100644
--- a/test/geometry/closestPair.double.cpp
+++ b/test/geometry/closestPair.double.cpp
@@ -10,7 +10,7 @@ constexpr ll INF = LL::INF;
//strict convex hull
double naive(const vector<pt>& ps) {
double opt = LL::INF;
- for (ll i = 0; i < sz(ps); i++) {
+ for (ll i = 0; i < ssize(ps); i++) {
for (ll j = 0; j < i; j++) {
opt = min(opt, norm(ps[i] - ps[j]));
}
diff --git a/test/geometry/convexHull.cpp b/test/geometry/convexHull.cpp
index 788a634..0ca52a2 100644
--- a/test/geometry/convexHull.cpp
+++ b/test/geometry/convexHull.cpp
@@ -9,7 +9,7 @@ constexpr ll EPS = 0;
//strict convex hull
ll isConvexHull(const vector<pt>& ps, const vector<pt>& hull) {
- ll n = sz(hull) - 1;
+ ll n = ssize(hull) - 1;
if (n == 0) {
for (pt p : ps) if (p != hull[0]) return 1;
return 0;
@@ -67,7 +67,7 @@ void performance_test() {
t.start();
auto a = convexHull(ps);
t.stop();
- hash_t hash = sz(a);
+ hash_t hash = ssize(a);
if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
}
diff --git a/test/geometry/delaunay.cpp b/test/geometry/delaunay.cpp
index 5740b95..b824ad8 100644
--- a/test/geometry/delaunay.cpp
+++ b/test/geometry/delaunay.cpp
@@ -6,28 +6,27 @@ auto cross(pt p, pt a, pt b) {return cross(a - p, b - p);}
#pragma GCC diagnostic ignored "-Wunused-variable"
#include <geometry/delaunay.cpp>
+
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--; //allow collinear points!
- 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--; // allow collinear points
+ 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;
}
lll area(const vector<pt>& poly) { //poly[0] == poly.back()
lll 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 res;
}
@@ -89,15 +88,15 @@ void stress_test(ll range) {
hull.pop_back();
auto got = delaunay(ps);
- if (sz(got) % 3 != 0) cerr << "error: not triangles" << FAIL;
- if (sz(got) / 3 + sz(hull) - 3 + 1 != 2 * sz(ps) - 4) cerr << "error: wrong number" << FAIL;
+ if (ssize(got) % 3 != 0) cerr << "error: not triangles" << FAIL;
+ if (ssize(got) / 3 + ssize(hull) - 3 + 1 != 2 * ssize(ps) - 4) cerr << "error: wrong number" << FAIL;
//all triangles should be oriented ccw
lll gotArea = 0;
- for (int i = 0; i < sz(got); i += 3) gotArea += cross(got[i], got[i+1], got[i+2]);
+ for (int i = 0; i < ssize(got); i += 3) gotArea += cross(got[i], got[i+1], got[i+2]);
if (gotArea != expectedArea) cerr << "error: wrong area" << FAIL;
- for (int i = 0; i < sz(got); i++) {
+ for (int i = 0; i < ssize(got); i++) {
int ii = i + 1;
if (i / 3 != ii / 3) ii -= 3;
for (int j = 0; j < i; j++) {
@@ -111,7 +110,7 @@ void stress_test(ll range) {
for (pt p : ps) seen |= p == got[i];
if (!seen) cerr << "error: invalid point" << FAIL;
}
- for (int i = 0; i < sz(got); i += 3) {
+ for (int i = 0; i < ssize(got); i += 3) {
for (pt p : ps) {
if (p == got[i]) continue;
if (p == got[i+1]) continue;
@@ -131,7 +130,7 @@ void performance_test() {
t.start();
auto got = delaunay(ps);
t.stop();
- hash_t hash = sz(got);
+ hash_t hash = ssize(got);
if (t.time > 500) cerr << "too slow: " << t.time << FAIL;
cerr << "tested performance: " << t.time << "ms (hash: " << hash << ")" << endl;
}
diff --git a/test/geometry/formulas.cpp b/test/geometry/formulas.cpp
index d63d431..f472e1f 100644
--- a/test/geometry/formulas.cpp
+++ b/test/geometry/formulas.cpp
@@ -107,7 +107,7 @@ void test_uniqueAngle(ll range) {
if (it->second != expected) cerr << "error: inconsistent" << FAIL;
queries++;
}
- cerr << "tested uniqueAngle: " << queries << " (" << sz(seen) << ")" << endl;
+ cerr << "tested uniqueAngle: " << queries << " (" << ssize(seen) << ")" << endl;
}
int main() {
diff --git a/test/geometry/hpi.cpp b/test/geometry/hpi.cpp
index a2326bc..e22e8c6 100644
--- a/test/geometry/hpi.cpp
+++ b/test/geometry/hpi.cpp
@@ -1,4 +1,6 @@
#include "../util.h"
+#define sz(X) (ll)::size(X)
+#define all(X) ::begin(X), ::end(X)
constexpr ll EPS = 0;
#define double ll
#define polar polar<ll>
@@ -14,10 +16,10 @@ ll sgn(ll x) {
//https://cp-algorithms.com/geometry/halfplane-intersection.html
namespace cpalgo {
// Redefine epsilon and infinity as necessary. Be mindful of precision errors.
- const long double eps = 1e-9, inf = 1e9;
+ const long double eps = 1e-9, inf = 1e9;
// Basic point/vector struct.
- struct Point {
+ struct Point {
long double x, y;
explicit Point(long double x_ = 0, long double y_ = 0) : x(x_), y(y_) {}
@@ -26,23 +28,23 @@ namespace cpalgo {
// Addition, substraction, multiply by constant, dot product, cross product.
friend Point operator + (const Point& p, const Point& q) {
- return Point(p.x + q.x, p.y + q.y);
+ return Point(p.x + q.x, p.y + q.y);
}
- friend Point operator - (const Point& p, const Point& q) {
- return Point(p.x - q.x, p.y - q.y);
+ friend Point operator - (const Point& p, const Point& q) {
+ return Point(p.x - q.x, p.y - q.y);
}
- friend Point operator * (const Point& p, const long double& k) {
- return Point(p.x * k, p.y * k);
- }
+ friend Point operator * (const Point& p, const long double& k) {
+ return Point(p.x * k, p.y * k);
+ }
friend long double dot(const Point& p, const Point& q) {
return p.x * q.x + p.y * q.y;
}
- friend long double cross(const Point& p, const Point& q) {
- return p.x * q.y - p.y * q.x;
+ friend long double cross(const Point& p, const Point& q) {
+ return p.x * q.y - p.y * q.x;
}
friend std::ostream& operator<<(std::ostream& os, const Point& p) {
@@ -53,10 +55,10 @@ namespace cpalgo {
};
// Basic half-plane struct.
- struct Halfplane {
+ struct Halfplane {
// 'p' is a passing point of the line and 'pq' is the direction vector of the line.
- Point p, pq;
+ Point p, pq;
long double angle;
Halfplane() {}
@@ -66,16 +68,16 @@ namespace cpalgo {
Halfplane(array<pt, 2> ps) : Halfplane(ps[0], ps[1]) {}
Halfplane(hp h) : Halfplane(h.from, h.to) {}
- // Check if point 'r' is outside this half-plane.
+ // Check if point 'r' is outside this half-plane.
// Every half-plane allows the region to the LEFT of its line.
bool out(const Point& r) {
- return cross(pq, r - p) < -eps;
+ return cross(pq, r - p) < -eps;
}
- // Comparator for sorting.
- bool operator < (const Halfplane& e) const {
+ // Comparator for sorting.
+ bool operator < (const Halfplane& e) const {
return angle < e.angle;
- }
+ }
// Intersection point of the lines of two half-planes. It is assumed they're never parallel.
friend Point inter(const Halfplane& s, const Halfplane& t) {
@@ -89,13 +91,13 @@ namespace cpalgo {
};
// Actual algorithm
- vector<Point> hp_intersect(vector<Halfplane>& H) {
+ vector<Point> hp_intersect(vector<Halfplane>& H) {
/*Point box[4] = { // Bounding box in CCW order
- Point(inf, inf),
- Point(-inf, inf),
- Point(-inf, -inf),
- Point(inf, -inf)
+ Point(inf, inf),
+ Point(-inf, inf),
+ Point(-inf, -inf),
+ Point(inf, -inf)
};
for(int i = 0; i<4; i++) { // Add bounding box half-planes.
@@ -181,7 +183,7 @@ void test_check(ll range) {
auto b = Random::line(range);
auto c = b;
while (cross(b[0] - b[1], c[0] - c[1]) == 0) c = Random::line(range);
-
+
bool got = hp(a[0], a[1]).check(hp(b[0], b[1]), hp(c[0], c[1]));
bool expected = naiveCheck(a, b, c);
diff --git a/test/geometry/polygon.cpp b/test/geometry/polygon.cpp
index 643ea70..29d3251 100644
--- a/test/geometry/polygon.cpp
+++ b/test/geometry/polygon.cpp
@@ -135,7 +135,7 @@ void test_insideConvex(ll range) {
// convex hull without duplicates, h[0] != h.back()
// apply comments if border counts as inside
bool insideOrOnConvex(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;
while (l + 1 < r) {
int m = (l + r) / 2;
@@ -155,7 +155,7 @@ void test_minkowski(ll range) {
auto got = minkowski(A, B);
bool convex = true;
- for (int i = 0; i < sz(got); i++) convex &= cross(got[i], got[(i+1) % sz(got)], got[(i+2) % sz(got)]) >= 0;
+ for (int i = 0; i < ssize(got); i++) convex &= cross(got[i], got[(i+1) % ssize(got)], got[(i+2) % ssize(got)]) >= 0;
if (!convex) cerr << "error: not convex" << FAIL;
for (pt a : A) {
@@ -172,19 +172,19 @@ double naive_dist(const vector<pt>& ps, const vector<pt>& qs) {
//check if intersect
double res = LD::INF;
bool intersect = true;
- for (int i = 0; i < sz(qs); i++) {
+ for (int i = 0; i < ssize(qs); i++) {
bool sep = true;
for (pt p : ps) {
- res = min(res, distToSegment(qs[i], qs[(i+1) % sz(qs)], p));
- sep &= cross(qs[i], qs[(i+1) % sz(qs)], p) <= 0;
+ res = min(res, distToSegment(qs[i], qs[(i+1) % ssize(qs)], p));
+ sep &= cross(qs[i], qs[(i+1) % ssize(qs)], p) <= 0;
}
if (sep) intersect = false;
}
- for (int i = 0; i < sz(ps); i++) {
+ for (int i = 0; i < ssize(ps); i++) {
bool sep = true;
for (pt q : qs) {
- res = min(res, distToSegment(ps[i], ps[(i+1) % sz(ps)], q));
- sep &= cross(ps[i], ps[(i+1) % sz(ps)], q) <= 0;
+ res = min(res, distToSegment(ps[i], ps[(i+1) % ssize(ps)], q));
+ sep &= cross(ps[i], ps[(i+1) % ssize(ps)], q) <= 0;
}
if (sep) intersect = false;
}
@@ -263,10 +263,10 @@ void test_intersect(ll range) {
}
}
}
- if (sz(expected) > 1 && expected[0] == expected[1]) expected.pop_back();
+ if (ssize(expected) > 1 && expected[0] == expected[1]) expected.pop_back();
- sort(all(got));
- sort(all(expected));
+ ranges::sort(got);
+ ranges::sort(expected);
if (got != expected) cerr << "error" << FAIL;
diff --git a/test/geometry/segmentIntersection.cpp b/test/geometry/segmentIntersection.cpp
index 6d3ddd6..5271563 100644
--- a/test/geometry/segmentIntersection.cpp
+++ b/test/geometry/segmentIntersection.cpp
@@ -40,7 +40,7 @@ vector<seg> randomSegs(int n, ll range) {
}
bool naive(vector<seg>& segs) {
- for (ll i = 0; i < sz(segs); i++) {
+ for (ll i = 0; i < ssize(segs); i++) {
for (ll j = 0; j < i; j++) {
if (segmentIntersection(segs[i].a, segs[i].b, segs[j].a, segs[j].b)) return true;
}
diff --git a/test/geometry/sortAround.cpp b/test/geometry/sortAround.cpp
index a27edc8..42ea86b 100644
--- a/test/geometry/sortAround.cpp
+++ b/test/geometry/sortAround.cpp
@@ -24,7 +24,7 @@ void test_tiny() {
};
auto got = expected;
for (int i = 0; i < 100'000; i++) {
- shuffle(all(got), Random::rng);
+ ranges::shuffle(got, Random::rng);
sortAround(0, got);
if (got != expected) cerr << "error" << FAIL;
}
@@ -51,8 +51,8 @@ void stress_test(ll range) {
auto isLeft = [&](pt p){return real(p - c) < 0 || (real(p - c) == 0 && imag(p - c) < 0);};
auto isCCW = [&](pt a, pt b){return cross(c, a, b) > 0;};
- if (!is_partitioned(all(ps), isLeft)) cerr << "error 1" << FAIL;
- auto mid = partition_point(all(ps), isLeft);
+ if (!ranges::is_partitioned(ps, isLeft)) cerr << "error 1" << FAIL;
+ auto mid = ranges::partition_point(ps, isLeft);
if (!is_sorted(ps.begin(), mid, isCCW)) cerr << "error 2" << FAIL;
if (!is_sorted(mid, ps.end(), isCCW)) cerr << "error 3" << FAIL;
queries += n;
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-23 18:37:23 +0000