src/geo2d/aunion/pos/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../ds/po/lib.hpp" | ||
| 4 | #include "../../ins/ll/lib.hpp" | ||
| 5 | #include "../../pred/is_ins_sl/lib.hpp" | ||
| 6 | |||
| 7 | namespace tifa_libs { | ||
| 8 | |||
| 9 | // @return ans, which ans[i] means area covered at least i+1 times | ||
| 10 | //! unique {@code pos} first | ||
| 11 | template <std::floating_point FP> | ||
| 12 | 50 | CEXP vec<FP> aunion_Pos(vec<polygon<FP>> CR pos) NE { | |
| 13 | 50 | u32 n = (u32)pos.size(); | |
| 14 | 50 | vvecpt<point<FP>> segs(n); | |
| 15 |
8/8✓ Branch 1 taken 23801783 times.
✓ Branch 2 taken 23989036 times.
✓ Branch 4 taken 15941598 times.
✓ Branch 5 taken 7860185 times.
✓ Branch 7 taken 23942620 times.
✓ Branch 8 taken 15988014 times.
✓ Branch 10 taken 15971738 times.
✓ Branch 11 taken 7970882 times.
|
47790819 | auto chk = [](point<FP> CR u, line<FP> CR e) NE { return !((u < e.l && u < e.r) || (u > e.l && u > e.r)); }; |
| 16 | 92882 | auto cut = [&](line<FP> CR e, u32 i) NE { | |
| 17 | 46416 | const line<FP> le{e.l, e.r}; | |
| 18 | 92832 | vecp<point<FP>, int> evt{{e.l, 0}, {e.r, 0}}; | |
| 19 |
2/2✓ Branch 0 taken 71431800 times.
✓ Branch 1 taken 46416 times.
|
71478216 | flt_ (u32, j, 0, n) { |
| 20 |
2/2✓ Branch 0 taken 46416 times.
✓ Branch 1 taken 71385384 times.
|
71431800 | if (i == j) continue; |
| 21 | 71385384 | auto CR pj = pos[j]; | |
| 22 |
2/2✓ Branch 1 taken 285541536 times.
✓ Branch 2 taken 71385384 times.
|
356926920 | flt_ (u32, k, 0, pj.size()) { |
| 23 | 285541536 | const line<FP> s{pj[k], pj[pj.next(k)]}; | |
| 24 |
6/6✓ Branch 1 taken 6452 times.
✓ Branch 2 taken 285535084 times.
✓ Branch 4 taken 3226 times.
✓ Branch 5 taken 3226 times.
✓ Branch 6 taken 3226 times.
✓ Branch 7 taken 285538310 times.
|
285541536 | if (!le.toleft(s.l) && !le.toleft(s.r)) evt.emplace_back(s.l, 0), evt.emplace_back(s.r, 0); |
| 25 |
2/2✓ Branch 1 taken 47559938 times.
✓ Branch 2 taken 237978372 times.
|
285538310 | else if (is_ins_SL(s, le)) { |
| 26 |
5/6✓ Branch 2 taken 23778223 times.
✓ Branch 3 taken 23781715 times.
✓ Branch 5 taken 23778223 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 23778223 times.
✓ Branch 8 taken 23781715 times.
|
47559938 | if (point<FP> u = ins_LL(le, s); le.toleft(s.l) < 0 && le.toleft(s.r) >= 0) evt.emplace_back(u, -1); |
| 27 |
5/6✓ Branch 1 taken 23781715 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 23778223 times.
✓ Branch 5 taken 3492 times.
✓ Branch 6 taken 23778223 times.
✓ Branch 7 taken 3492 times.
|
23781715 | else if (le.toleft(s.l) >= 0 && le.toleft(s.r) < 0) evt.emplace_back(u, 1); |
| 28 | } | ||
| 29 | } | ||
| 30 | } | ||
| 31 |
2/2✓ Branch 2 taken 23208 times.
✓ Branch 3 taken 23208 times.
|
46416 | if (sort(evt); e.l > e.r) reverse(evt); |
| 32 | 46416 | int sum = 0; | |
| 33 |
1/2✓ Branch 1 taken 31816525 times.
✗ Branch 2 not taken.
|
31816525 | flt_ (u32, i, 0, (u32)evt.size()) { |
| 34 | 31816525 | sum += evt[i].second; | |
| 35 | 31816525 | point<FP> u = evt[i].first, v = evt[i + 1].first; | |
| 36 |
7/8✓ Branch 1 taken 31810943 times.
✓ Branch 2 taken 5582 times.
✓ Branch 4 taken 15979876 times.
✓ Branch 5 taken 15831067 times.
✓ Branch 7 taken 15979876 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 15979876 times.
✓ Branch 10 taken 15836649 times.
|
31816525 | if (!(u == v) && chk(u, e) && chk(v, e)) segs[(u32)sum].emplace_back(u, v); |
| 37 |
2/2✓ Branch 1 taken 46416 times.
✓ Branch 2 taken 31770109 times.
|
31816525 | if (v == e.r) break; |
| 38 | } | ||
| 39 | 46416 | }; | |
| 40 |
2/2✓ Branch 1 taken 11604 times.
✓ Branch 2 taken 50 times.
|
11654 | flt_ (u32, i, 0, (u32)pos.size()) { |
| 41 | 11604 | auto CR pi = pos[i]; | |
| 42 |
2/2✓ Branch 6 taken 46416 times.
✓ Branch 7 taken 11604 times.
|
58020 | flt_ (u32, k, 0, pi.size()) cut({pi[k], pi[pi.next(k)]}, i); |
| 43 | } | ||
| 44 | 50 | vec<FP> ans(n); | |
| 45 |
2/2✓ Branch 0 taken 11604 times.
✓ Branch 1 taken 50 times.
|
11654 | flt_ (u32, i, 0, n) { |
| 46 | 11604 | sort(segs[i]); | |
| 47 | 11604 | FP sum = 0; | |
| 48 | 11604 | u32 cnt = 0; | |
| 49 |
2/2✓ Branch 2 taken 15980985 times.
✓ Branch 3 taken 11604 times.
|
15992589 | flt_ (u32, j, 0, (u32)segs[i].size()) { |
| 50 |
6/6✓ Branch 0 taken 15977950 times.
✓ Branch 1 taken 3035 times.
✓ Branch 7 taken 1109 times.
✓ Branch 8 taken 15976841 times.
✓ Branch 9 taken 1109 times.
✓ Branch 10 taken 15979876 times.
|
15980985 | if (j > 0 && segs[i][j] == segs[i][j - 1]) segs[i + (++cnt)].push_back(segs[i][j]); |
| 51 | 15979876 | else cnt = 0, sum += segs[i][j].first ^ segs[i][j].second; | |
| 52 | } | ||
| 53 | 11604 | ans[i] = sum / 2; | |
| 54 | } | ||
| 55 | 50 | return ans; | |
| 56 | 50 | } | |
| 57 | |||
| 58 | } // namespace tifa_libs | ||
| 59 |