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 <noob999noob999@gmail.com>

1 files changed, 146 insertions, 0 deletions

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 <geometry/formulas.cpp>
+#undef ll
+ll sgn(double x) {
+	return (x > EPS) - (x < -EPS);
+}
+#include <geometry/triangle.cpp>
+#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);
+}