From 8d11c6c8213f46f0fa19826917c255edd5d43cb1 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sun, 28 Jul 2024 22:54:40 +0200 Subject: Test (#4) * update * moved content in subdir * rename file * add test setup * add test setup * add github action * automaticly test all cpp files * timeout after 10s * setulimit and dont zero memory * test build pdf * install latexmk * update * update * ngerman * fonts * removed old code * add first test * added tests * test in sorted order * more tests * simplified test * more tests * fix suffix tree * fixes and improvements * done ust lst directly * fix swap * add links to pdf * fix constants * add primorial * add comment * various improvements * more tests * added missing stuf * more tests * fix tests * more tests * more tests * more tests * fix recursion? * test trie * more tests * only use python temporarily for listings * only use python temporarily for listings * more tests * fix longestCommonSubstring * more tests * more tests * made code more similiar * fix? * more tests * more tests * more tests * add ahoCorasick test + limit 4GB stack size * more tests * fix test * add additional test * more tests * more tests * fix? * better fix * fix virtual tree * more tests * more tests * recursive closest pair * more tests * decrease limit * new tests * more tests * fix name * more tests * add test * new test * more tests * more tests * more tests * more tests * new test and content * new code * new code * larger tests * fix and test * new test * new test * update pdf * remove comments * new test * more tests * more testcases * more tests * increased limit * more tests * more tests * more tests * new tests * more tests * shortened code * new test * add basic tests for bigint * more tests * removed old files * new test * ignore some files * more auto more ccw * fix test * more tests * fix * new tests * more tests * more tests * stronger test * actually verify delaunay... * more tests * fix header * more tests * run tests parallel? * test parralel? * add --missing * separate workflows * test * is the pdf checked? * separate workflows * fix workflow * more workflows --------- Co-authored-by: Yidi --- test/geometry/formulas.cpp | 127 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 127 insertions(+) create mode 100644 test/geometry/formulas.cpp (limited to 'test/geometry/formulas.cpp') diff --git a/test/geometry/formulas.cpp b/test/geometry/formulas.cpp new file mode 100644 index 0000000..d63d431 --- /dev/null +++ b/test/geometry/formulas.cpp @@ -0,0 +1,127 @@ +#include "../util.h" +constexpr ll EPS = 0; +#define double ll +#define polar polar +#include +#undef polar +#undef double + +void test_dot(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto p = Random::point(-range, range); + auto q = Random::point(-range, range); + + ll expected = real(p) * real(q) + imag(p) * imag(q); + ll got = dot(p, q); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + cerr << "tested dot: " << queries << endl; +} + +void test_norm(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto p = Random::point(-range, range); + + ll expected = real(p) * real(p) + imag(p) * imag(p); + ll got = norm(p); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + cerr << "tested norm: " << queries << endl; +} + +void test_cross(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto p = Random::point(-range, range); + auto q = Random::point(-range, range); + + ll expected = real(p) * imag(q) - imag(p) * real(q); + ll got = cross(p, q); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + cerr << "tested cross1: " << queries << endl; + + queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto a = Random::point(-range, range); + auto b = Random::point(-range, range); + auto c = Random::point(-range, range); + + ll expected = cross(b - a, c - a); + ll got = cross(a, b, c); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + cerr << "tested cross2: " << queries << endl; +} + +void test_ccw(ll range) { + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + auto a = Random::point(-range, range); + auto b = Random::point(-range, range); + auto c = Random::point(-range, range); + + ll expected = cross(a, b, c); + if (expected < 0) expected = -1; + if (expected > 0) expected = 1; + ll got = ccw(a, b, c); + + if (got != expected) cerr << "got: " << got << ", expected: " << expected << FAIL; + queries++; + } + cerr << "tested ccw: " << queries << endl; +} + +void test_isCoplanar(ll range) {(void) range;}// cant check this... + +void test_uniqueAngle(ll range) { + auto lessPt = [](pt a, pt b){ + if (real(a) != real(b)) return real(a) < real(b); + return imag(a) < imag(b); + }; + map seen(lessPt); + + ll queries = 0; + for (int tries = 0; tries < 100'000; tries++) { + pt expected = Random::point(-sqrt(range), sqrt(range)); + ll g = abs(gcd(real(expected), imag(expected))); + if (g == 0) continue; + expected /= g; + + pt rot = Random::point(-sqrt(range), sqrt(range)); + if (norm(rot) == 0) continue; + + pt got = uniqueAngle(expected * rot, pt(Random::integer(1, sqrt(range)), 0) * rot); + auto it = seen.emplace(got, expected).first; + + if (it->second != expected) cerr << "error: inconsistent" << FAIL; + queries++; + } + cerr << "tested uniqueAngle: " << queries << " (" << sz(seen) << ")" << endl; +} + +int main() { + test_dot(100); + test_dot(1'000'000'000); + test_norm(100); + test_norm(1'000'000'000); + test_cross(100); + test_cross(1'000'000'000); + test_ccw(100); + test_ccw(1'000'000'000); + test_isCoplanar(100); + test_isCoplanar(1'000'000'000); + test_uniqueAngle(100); + test_uniqueAngle(10'000); + test_uniqueAngle(1'000'000'000); +} -- cgit v1.2.3