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/hpi.cpp | 68 -------------------------------------------------------- 1 file changed, 68 deletions(-) delete mode 100644 geometry/hpi.cpp (limited to 'geometry/hpi.cpp') diff --git a/geometry/hpi.cpp b/geometry/hpi.cpp deleted file mode 100644 index 3509e0e..0000000 --- a/geometry/hpi.cpp +++ /dev/null @@ -1,68 +0,0 @@ -constexpr ll inf = 0x1FFF'FFFF'FFFF'FFFF;//THIS CODE IS WIP - -bool left(pt p) {return real(p) < 0 || - (real(p) == 0 && imag(p) < 0);} -struct hp { - pt from, to; - - hp(pt a, pt b) : from(a), to(b) {} - hp(pt dummy) : hp(dummy, dummy) {} - - bool dummy() const {return from == to;} - pt dir() const {return dummy() ? to : to - from;} - bool operator<(const hp& o) const { - if (left(dir()) != left(o.dir())) - return left(dir()) > left(o.dir()); - return cross(dir(), o.dir()) > 0; - } - - using lll = __int128; - using ptl = complex; - ptl mul(lll m, ptl p) const {return m*p;}//ensure 128bit - - bool check(const hp& a, const hp& b) const { - if (dummy() || b.dummy()) return false; - if (a.dummy()) { - ll ort = sgn(cross(b.dir(), dir())); - if (ort == 0) return cross(from, to, a.from) < 0; - return cross(b.dir(), a.dir()) * ort > 0; - } - ll y = cross(a.dir(), b.dir()); - ll z = cross(b.from - a.from, b.dir()); - ptl i = mul(y, a.from) + mul(z, a.dir()); //intersect a and b - // check if i is outside/right of x - return imag(conj(mul(sgn(y),dir()))*(i-mul(y,from))) < 0; - } -}; - -constexpr ll lim = 2e9+7; - -deque intersect(vector hps) { - hps.push_back(hp(pt{lim+1,-1})); - hps.push_back(hp(pt{lim+1,1})); - sort(all(hps)); - - deque dq = {hp(pt{-lim, 1})}; - for (auto x : hps) { - while (sz(dq) > 1 && x.check(dq.end()[-1], dq.end()[-2])) - dq.pop_back(); - while (sz(dq) > 1 && x.check(dq[0], dq[1])) - dq.pop_front(); - - if (cross(x.dir(), dq.back().dir()) == 0) { - if (dot(x.dir(), dq.back().dir()) < 0) return {}; - if (cross(x.from, x.to, dq.back().from) < 0) - dq.pop_back(); - else continue; - } - dq.push_back(x); - } - - while (sz(dq) > 2 && dq[0].check(dq.end()[-1], dq.end()[-2])) - dq.pop_back(); - while (sz(dq) > 2 && dq.end()[-1].check(dq[0], dq[1])) - dq.pop_front(); - - if (sz(dq) < 3) return {}; - return dq; -} -- cgit v1.2.3