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/triangle.cpp | 146 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 146 insertions(+) create mode 100644 test/geometry/triangle.cpp (limited to 'test/geometry/triangle.cpp') diff --git a/test/geometry/triangle.cpp b/test/geometry/triangle.cpp new file mode 100644 index 0000000..dc620ee --- /dev/null +++ b/test/geometry/triangle.cpp @@ -0,0 +1,146 @@ +#include "../util.h" +constexpr double EPS = 1e-6; +#define ll double +double gcd(double x, double /**/) {return x;} //hacky +#include +#undef ll +ll sgn(double x) { + return (x > EPS) - (x < -EPS); +} +#include +#include "../geometry.h" + +// Entfernung von Punkt p zur Geraden durch a-b. 2d und 3d +double distToLine(pt a, pt b, pt p) { + return abs(cross(p - a, b - a)) / abs(b - a); +} + +void test_centroid(ll range) { + int queries = 0; + for (int tries = 0; tries < 1'000'000; tries++) { + auto [a, b, c] = Random::triangle(range); + + pt center = centroid(a, b, c); + + if (distToLine(2.0*a, c+b, 2.0*center) > 1e-6) cerr << "error: 1" << FAIL; + if (distToLine(2.0*b, c+a, 2.0*center) > 1e-6) cerr << "error: 2" << FAIL; + if (distToLine(2.0*c, a+b, 2.0*center) > 1e-6) cerr << "error: 3" << FAIL; + queries++; + } + cerr << "tested centroid: " << queries << endl; +} + +void test_area(ll range) { + int queries = 0; + for (int tries = 0; tries < 1'000'000; tries++) { + auto [a, b, c] = Random::triangle(range); + + auto gotA = 2*area(a, b, c); + auto gotB = 2*area(abs(a-b), abs(b-c), abs(c-a)); + auto expected = llround(gotA); + + if (float_error(gotA, expected) > 1e-6) cerr << "error: 1" << FAIL; + if (float_error(gotB, expected) > 1e-3) cerr << "error: 2" << FAIL; + queries++; + } + cerr << "tested area: " << queries << endl; +} + +void test_inCenter(ll range) { + int queries = 0; + for (int tries = 0; tries < 1'000'000; tries++) { + auto [a, b, c] = Random::triangle(range); + + pt center = inCenter(a, b, c); + + double da = distToLine(a, b, center); + double db = distToLine(b, c, center); + double dc = distToLine(c, a, center); + + double avg = (da + db + dc) / 3.0; + + if (float_error(da, avg) > 1e-6) cerr << "error: 1" << FAIL; + if (float_error(db, avg) > 1e-6) cerr << "error: 2" << FAIL; + if (float_error(dc, avg) > 1e-6) cerr << "error: 3" << FAIL; + queries++; + } + cerr << "tested inCenter: " << queries << endl; +} + +void test_circumCenter(ll range) { + int queries = 0; + for (int tries = 0; tries < 1'000'000; tries++) { + auto [a, b, c] = Random::triangle(range); + + pt center = circumCenter(a, b, c); + + double da = abs(center - a); + double db = abs(center - b); + double dc = abs(center - c); + + double avg = (da + db + dc) / 3.0; + + if (float_error(da, avg) > 1e-6) cerr << "error: 1" << FAIL; + if (float_error(db, avg) > 1e-6) cerr << "error: 2" << FAIL; + if (float_error(dc, avg) > 1e-6) cerr << "error: 3" << FAIL; + queries++; + } + cerr << "tested circumCenter: " << queries << endl; +} + +void test_insideOutCenter(ll range) { + int queries = 0; + for (int tries = 0; tries < 1'000'000; tries++) { + auto [a, b, c] = Random::triangle(range); + pt p = Random::integerPoint(range); + + pt center = circumCenter(a, b, c); + + double da = abs(center - a); + double db = abs(center - b); + double dc = abs(center - c); + double dp = abs(center - p); + + double avg = (da + db + dc) / 3.0; + + int expected = dp < avg ? 1 : -1; + if (float_error(dp, avg) < 1e-9) expected = 0; + + if (insideOutCenter(a, b, c, p) != expected) cerr << "error" << FAIL; + + queries++; + } + cerr << "tested insideOutCenter: " << queries << endl; +} + +void test_similar(ll range) { + int queries = 0; + for (int tries = 0; tries < 1'000'000; tries++) { + auto [a, b, c] = Random::triangle(sqrt(range)); + pt rot = Random::integerPoint(sqrt(range)); + pt add = Random::integerPoint(range); + + pt d = rot * a + add; + pt e = rot * b + add; + pt f = rot * c + add; + + if (!similar(a, b, c, d, e, f)) cerr << "error" << FAIL; + queries++; + } + cerr << "tested similar: " << queries << endl; +} + +int main() { + test_centroid(100); + test_centroid(1'000'000'000); + test_area(100); + test_area(1'000'000'000); + test_inCenter(100); + test_inCenter(1'000'000'000); + test_circumCenter(100); + test_circumCenter(1'000'000'000); + test_insideOutCenter(100); + test_insideOutCenter(1'000'000'000); + test_similar(100); + test_similar(1'000'000'000); +} -- cgit v1.2.3