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/delaunay.cpp | 124 -------------------------------------------------- 1 file changed, 124 deletions(-) delete mode 100644 geometry/delaunay.cpp (limited to 'geometry/delaunay.cpp') diff --git a/geometry/delaunay.cpp b/geometry/delaunay.cpp deleted file mode 100644 index 1008b39..0000000 --- a/geometry/delaunay.cpp +++ /dev/null @@ -1,124 +0,0 @@ -using lll = __int128; -using pt = complex; - -constexpr pt INF_PT = pt(1e18, 1e18); - -bool circ(pt p, pt a, pt b, pt c) {// p in circle(A,B,C) - return imag((c-b)*conj(p-c)*(a-p)*conj(b-a)) < 0; -} - -struct QuadEdge { - QuadEdge* rot = nullptr; - QuadEdge* onext = nullptr; - pt orig = INF_PT; - bool used = false; - QuadEdge* rev() const {return rot->rot;} - QuadEdge* lnext() const {return rot->rev()->onext->rot;} - QuadEdge* oprev() const {return rot->onext->rot;} - pt dest() const {return rev()->orig;} -}; - -deque edgeData; - -QuadEdge* makeEdge(pt from, pt to) { - for (int j : {0,1,2,3}) edgeData.push_back({}); - auto e = edgeData.end() - 4; - for (int j : {0,1,2,3}) e[j].onext = e[j^3].rot = &e[j^(j>>1)]; - e[0].orig = from; - e[1].orig = to; - return &e[0]; -} - -void splice(QuadEdge* a, QuadEdge* b) { - swap(a->onext->rot->onext, b->onext->rot->onext); - swap(a->onext, b->onext); -} - -QuadEdge* connect(QuadEdge* a, QuadEdge* b) { - QuadEdge* e = makeEdge(a->dest(), b->orig); - splice(e, a->lnext()); - splice(e->rev(), b); - return e; -} - -bool valid(QuadEdge* e, QuadEdge* base) { - return cross(e->dest(), base->orig, base->dest()) < 0; -} - -template -QuadEdge* deleteAll(QuadEdge* e, QuadEdge* base) { - if (valid(e, base)) { - while (circ(base->dest(), base->orig, e->dest(), (ccw ? e->onext : e->oprev())->dest())) { - QuadEdge* t = ccw ? e->onext : e->oprev(); - splice(e, e->oprev()); - splice(e->rev(), e->rev()->oprev()); - e = t; - }} - return e; -} - -template -pair rec(IT l, IT r) { - int n = distance(l, r); - if (n <= 3) { - QuadEdge* a = makeEdge(l[0], l[1]); - if (n == 2) return {a, a->rev()}; - QuadEdge* b = makeEdge(l[1], l[2]); - splice(a->rev(), b); - int side = cross(l[0], l[1], l[2]); - QuadEdge* c = nullptr; - if (side != 0) c = connect(b, a); - if (side >= 0) return {a, b->rev()}; - else return {c->rev(), c}; - } - auto m = l + (n / 2); - auto [ldo, ldi] = rec(l, m); - auto [rdi, rdo] = rec(m, r); - while (true) { - if (cross(rdi->orig, ldi->orig, ldi->dest()) > 0) { - ldi = ldi->lnext(); - } else if (cross(ldi->orig, rdi->orig, rdi->dest()) < 0) { - rdi = rdi->rev()->onext; - } else break; - } - QuadEdge* base = connect(rdi->rev(), ldi); - if (ldi->orig == ldo->orig) ldo = base->rev(); - if (rdi->orig == rdo->orig) rdo = base; - while (true) { - QuadEdge* lcand = deleteAll(base->rev()->onext, base); - QuadEdge* rcand = deleteAll(base->oprev(), base); - if (!valid(lcand, base) && !valid(rcand, base)) break; - if (!valid(lcand, base) || (valid(rcand, base) && - circ(lcand->dest(), lcand->orig, rcand->orig, rcand->dest()))) { - base = connect(rcand, base->rev()); - } else { - base = connect(base->rev(), lcand->rev()); - }} - return {ldo, rdo}; -} - -vector delaunay(vector pts) { - if (sz(pts) <= 2) return {}; - sort(all(pts), [](const pt& a, const pt& b) { - if (real(a) != real(b)) return real(a) < real(b); - return imag(a) < imag(b); - }); - QuadEdge* r = rec(all(pts)).first; - vector edges = {r}; - while (cross(r->onext->dest(), r->dest(), r->orig) < 0) r = r->onext; - auto add = [&](QuadEdge* e){ - QuadEdge* cur = e; - do { - cur->used = true; - pts.push_back(cur->orig); - edges.push_back(cur->rev()); - cur = cur->lnext(); - } while (cur != e); - }; - add(r); - pts.clear(); - for (int i = 0; i < sz(edges); i++) { - if (!edges[i]->used) add(edges[i]); - } - return pts; -} -- cgit v1.2.3