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 --- geometry/polygon.cpp | 150 --------------------------------------------------- 1 file changed, 150 deletions(-) delete mode 100644 geometry/polygon.cpp (limited to 'geometry/polygon.cpp') diff --git a/geometry/polygon.cpp b/geometry/polygon.cpp deleted file mode 100644 index e3ce33e..0000000 --- a/geometry/polygon.cpp +++ /dev/null @@ -1,150 +0,0 @@ -// Flächeninhalt eines Polygons (nicht selbstschneidend). -// Punkte gegen den Uhrzeigersinn: positiv, sonst negativ. -double area(const vector& poly) { //poly[0] == poly.back() - double res = 0; - for (int i = 0; i + 1 < sz(poly); i++) - res += cross(poly[i], poly[i + 1]); - return 0.5 * res; -} - -// Anzahl drehungen einer Polyline um einen Punkt -// p nicht auf rand und poly[0] == poly.back() -// res != 0 or (res & 1) != 0 um inside zu prüfen bei -// selbstschneidenden Polygonen (definitions Sache) -ll windingNumber(pt p, const vector& poly) { - ll res = 0; - for (int i = 0; i + 1 < sz(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) && - cross(p, a, b) < 0) { - res += orientation(p, poly[i], poly[i + 1]); - }} - return res; -} - -// Testet, ob ein Punkt im Polygon liegt (beliebige Polygone). -// Ändere Zeile 32 falls rand zählt, poly[0] == poly.back() -bool inside(pt p, const vector& poly) { - bool in = false; - for (int i = 0; i + 1 < sz(poly); i++) { - pt a = poly[i], b = poly[i + 1]; - if (pointOnLineSegment(a, b, p)) return false; - if (real(a) > real(b)) swap(a,b); - if (real(a) <= real(p) && real(p) < real(b) && - cross(p, a, b) < 0) { - in ^= 1; - }} - return in; -} - -// convex hull without duplicates, h[0] != h.back() -// apply comments if border counts as inside -bool inside(pt p, const vector& hull) { - int l = 0, r = sz(hull) - 1; - if (cross(hull[0], hull[r], p) >= 0) return false; // > 0 - while (l + 1 < r) { - int m = (l + r) / 2; - if (cross(hull[0], hull[m], p) > 0) l = m; // >= 0 - else r = m; - } - return cross(hull[l], hull[r], p) > 0; // >= 0 -} - -void rotateMin(vector& 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()); -} - -// convex hulls without duplicates, h[0] != h.back() -vector minkowski(vector ps, vector qs) { - rotateMin(ps); - rotateMin(qs); - ps.push_back(ps[0]); - qs.push_back(qs[0]); - ps.push_back(ps[1]); - qs.push_back(qs[1]); - vector res; - for (ll i = 0, j = 0; i + 2 < sz(ps) || j + 2 < sz(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++; - if(c <= 0) j++; - } - return res; -} - -// convex hulls without duplicates, h[0] != h.back() -double dist(const vector& ps, const vector& qs) { - for (pt& q : qs) q *= -1; - auto p = minkowski(ps, qs); - p.push_back(p[0]); - double res = 0.0; - //bool intersect = true; - for (ll i = 0; i + 1 < sz(p); i++) { - //intersect &= cross(p[i], p[i+1] - p[i]) <= 0; - res = max(res, cross(p[i], p[i+1]-p[i]) / abs(p[i+1]-p[i])); - } - return res; -} - -bool left(pt of, pt p) {return cross(p, of) < 0 || - (cross(p, of) == 0 && dot(p, of) > 0);} - -// convex hulls without duplicates, hull[0] == hull.back() and -// hull[0] must be a convex point (with angle < pi) -// returns index of corner where dot(dir, corner) is maximized -int extremal(const vector& hull, pt dir) { - dir *= pt(0, 1); - int l = 0, r = sz(hull) - 1; - while (l + 1 < r) { - int m = (l + r) / 2; - pt dm = hull[m+1]-hull[m]; - pt dl = hull[l+1]-hull[l]; - if (left(dl, dir) != left(dl, dm)) { - if (left(dl, dm)) l = m; - else r = m; - } else { - if (cross(dir, dm) < 0) l = m; - else r = m; - }} - return r; -} - -// convex hulls without duplicates, hull[0] == hull.back() and -// hull[0] must be a convex point (with angle < pi) -// {} if no intersection -// {x} if corner is only intersection -// {a, b} segments (a,a+1) and (b,b+1) intersected (if only the -// border is intersected corners a and b are the start and end) -vector intersect(const vector& hull, pt a, pt b) { - int endA = extremal(hull, (a-b) * pt(0, 1)); - int endB = extremal(hull, (b-a) * pt(0, 1)); - // cross == 0 => line only intersects border - if (cross(hull[endA], a, b) > 0 || - cross(hull[endB], a, b) < 0) return {}; - - int n = sz(hull) - 1; - vector res; - for (auto _ : {0, 1}) { - int l = endA, r = endB; - if (r < l) r += n; - while (l + 1 < r) { - int m = (l + r) / 2; - if (cross(hull[m % n], a, b) <= 0 && - cross(hull[m % n], a, b) != hull(poly[endB], a, b)) - l = m; - else r = m; - } - if (cross(hull[r % n], a, b) == 0) l++; - res.push_back(l % n); - swap(endA, endB); - swap(a, b); - } - if (res[0] == res[1]) res.pop_back(); - return res; -} - -- cgit v1.2.3