src/geo2d/aunion/cs/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../ins/cc/lib.hpp" | ||
| 4 | #include "../../rel/cc/lib.hpp" | ||
| 5 | |||
| 6 | namespace tifa_libs { | ||
| 7 | |||
| 8 | // @return ans, which ans[i] means area covered at least i+1 times | ||
| 9 | template <std::floating_point FP> | ||
| 10 | 17 | CEXP vec<FP> aunion_Cs(vec<circle<FP>> CR cs) NE { | |
| 11 | struct arc_t { | ||
| 12 | point<FP> p; | ||
| 13 | FP _0, _1, _2; | ||
| 14 | 66056605 | CEXP auto operator<=>(arc_t CR r) CNE { | |
| 15 |
2/2✓ Branch 1 taken 55596484 times.
✓ Branch 2 taken 10460121 times.
|
66056605 | if (auto CR c = p <=> r.p; c) return c; |
| 16 |
2/2✓ Branch 1 taken 2439961 times.
✓ Branch 2 taken 8020160 times.
|
10460121 | if (auto CR c = comp(_0, r._0); c) return c; |
| 17 |
1/2✓ Branch 1 taken 8020160 times.
✗ Branch 2 not taken.
|
8020160 | if (auto CR c = comp(_1, r._1); c) return c; |
| 18 | ✗ | return comp(_2, r._2); | |
| 19 | } | ||
| 20 | CEXP bool operator==(arc_t CR r) CNE { return (*this <=> r) == 0; } | ||
| 21 | }; | ||
| 22 | 17 | cu32 n = (u32)cs.size(); | |
| 23 | 17 | vvec<arc_t> arcs(n); | |
| 24 | 20917 | auto cut = [&](circle<FP> CR ci, u32 i) NE { | |
| 25 | 10450 | vecp<FP, int> evt; | |
| 26 | 10450 | evt.emplace_back(-pi_v<FP>, 0), evt.emplace_back(pi_v<FP>, 0); | |
| 27 | 10450 | int init = 0; | |
| 28 |
2/2✓ Branch 0 taken 9474522 times.
✓ Branch 1 taken 10450 times.
|
9484972 | flt_ (u32, j, 0, n) { |
| 29 |
2/2✓ Branch 0 taken 10450 times.
✓ Branch 1 taken 9464072 times.
|
16135192 | if (i == j) continue; |
| 30 | 9464072 | circle<FP> CR cj = cs[j]; | |
| 31 |
8/8✓ Branch 2 taken 4186682 times.
✓ Branch 3 taken 5277390 times.
✓ Branch 4 taken 1512061 times.
✓ Branch 5 taken 2674621 times.
✓ Branch 6 taken 4498 times.
✓ Branch 7 taken 1507563 times.
✓ Branch 8 taken 2679119 times.
✓ Branch 9 taken 6784953 times.
|
9464072 | if (auto _ = relation_CC(ci, cj); is_lt(ci.r, cj.r) && (_ == RELCC::lyingin || _ == RELCC::touchin)) ++init; |
| 32 | 9464072 | const auto icij = ins_CC(ci, cj); | |
| 33 |
2/2✓ Branch 1 taken 6660670 times.
✓ Branch 2 taken 2803402 times.
|
9464072 | if (!icij) continue; |
| 34 |
2/2✓ Branch 3 taken 14942 times.
✓ Branch 4 taken 2788460 times.
|
2803402 | if (icij->first == icij->second) evt.emplace_back((icij->first - ci.o).arg(), 0); |
| 35 | else { | ||
| 36 | 2788460 | point<FP> dl = icij->first - ci.o, dr = icij->second - ci.o; | |
| 37 | 2788460 | FP argl = dl.arg(), argr = dr.arg(); | |
| 38 |
2/2✓ Branch 1 taken 493 times.
✓ Branch 2 taken 2787967 times.
|
2788460 | if (is_eq(argl, -pi_v<FP>)) argl = pi_v<FP>; |
| 39 |
2/2✓ Branch 1 taken 369 times.
✓ Branch 2 taken 2788091 times.
|
2788460 | if (is_eq(argr, -pi_v<FP>)) argr = pi_v<FP>; |
| 40 |
2/2✓ Branch 1 taken 1138816 times.
✓ Branch 2 taken 1649644 times.
|
2788460 | if (is_gt(argl, argr)) { |
| 41 | 1138816 | evt.emplace_back(argl, 1); | |
| 42 | 1138816 | evt.emplace_back(pi_v<FP>, -1); | |
| 43 | 1138816 | evt.emplace_back(-pi_v<FP>, 1); | |
| 44 | 1138816 | evt.emplace_back(argr, -1); | |
| 45 | 1649644 | } else evt.emplace_back(argl, 1), evt.emplace_back(argr, -1); | |
| 46 | } | ||
| 47 | } | ||
| 48 | 10450 | sort(evt); | |
| 49 | 10450 | int sum = init; | |
| 50 |
1/2✓ Branch 1 taken 6735603 times.
✗ Branch 2 not taken.
|
6735603 | flt_ (u32, i, 0, (u32)evt.size()) { |
| 51 | 6735603 | sum += evt[i].second; | |
| 52 |
2/2✓ Branch 3 taken 5568599 times.
✓ Branch 4 taken 1167004 times.
|
6735603 | if (!is_eq(evt[i].first, evt[i + 1].first)) arcs[(u32)sum].emplace_back(ci.o, ci.r, evt[i].first, evt[i + 1].first); |
| 53 |
2/2✓ Branch 2 taken 10450 times.
✓ Branch 3 taken 6725153 times.
|
6735603 | if (is_eq(evt[i + 1].first, pi_v<FP>)) break; |
| 54 | } | ||
| 55 | 10450 | }; | |
| 56 | 5568599 | auto oint = [](arc_t CR arc) NE { | |
| 57 |
2/2✓ Branch 1 taken 83 times.
✓ Branch 2 taken 5568516 times.
|
5568599 | if (auto [cc, cr, l, r] = arc; is_eq(r - l, pi_v<FP> * 2)) return 2 * pi_v<FP> * cr * cr; |
| 58 | 5568516 | else return cr * (cr * (r - l) + cc.x * (std::sin(r) - std::sin(l)) - cc.y * (std::cos(r) - std::cos(l))); | |
| 59 | }; | ||
| 60 |
2/2✓ Branch 2 taken 10450 times.
✓ Branch 3 taken 17 times.
|
10467 | flt_ (u32, i, 0, n) cut(cs[i], i); |
| 61 | 5560626 | auto eq = [](arc_t CR u, arc_t CR v) NE { | |
| 62 | 5560626 | auto [u1, u2, u3, u4] = u; | |
| 63 | 5560626 | auto [v1, v2, v3, v4] = v; | |
| 64 |
5/8✓ Branch 1 taken 3915531 times.
✓ Branch 2 taken 1645095 times.
✓ Branch 4 taken 3728233 times.
✓ Branch 5 taken 187298 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 3728233 times.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
|
5560626 | return u1 == v1 && is_eq(u2, v2) && is_eq(u3, v3) && is_eq(u4, v4); |
| 65 | }; | ||
| 66 | 17 | vec<FP> ans(n); | |
| 67 |
2/2✓ Branch 0 taken 10450 times.
✓ Branch 1 taken 17 times.
|
10467 | flt_ (u32, i, 0, n) { |
| 68 | 10450 | FP sum = 0; | |
| 69 | 10450 | sort(arcs[i]); | |
| 70 | 10450 | u32 cnt = 0; | |
| 71 |
2/2✓ Branch 2 taken 5568599 times.
✓ Branch 3 taken 10450 times.
|
5579049 | flt_ (u32, j, 0, (u32)arcs[i].size()) |
| 72 |
4/6✓ Branch 0 taken 5560626 times.
✓ Branch 1 taken 7973 times.
✗ Branch 7 not taken.
✓ Branch 8 taken 5560626 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 5568599 times.
|
5568599 | if (j > 0 && eq(arcs[i][j], arcs[i][j - 1])) arcs[i + (++cnt)].push_back(arcs[i][j]); |
| 73 | 5568599 | else cnt = 0, sum += oint(arcs[i][j]); | |
| 74 | 10450 | ans[i] = sum / 2; | |
| 75 | } | ||
| 76 | 17 | return ans; | |
| 77 | 17 | } | |
| 78 | |||
| 79 | } // namespace tifa_libs | ||
| 80 |