test/cpv_local/geo2d/ins_hps.bzoj3199.cpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | // competitive-verifier: LOCALCASE test/cpv_local/_data/bzoj/3199 | ||
| 2 | |||
| 3 | #include "../../../src/geo2d/ins_hps/lib.hpp" | ||
| 4 | #include "../../../src/geo2d/proj/lib.hpp" | ||
| 5 | #include "../../../src/graph/ds/alist/lib.hpp" | ||
| 6 | #include "../../../src/graph/sp/dijkstra/lib.hpp" | ||
| 7 | |||
| 8 | using namespace tifa_libs; | ||
| 9 | using std::cin, std::cout; | ||
| 10 | using data_t = f128; | ||
| 11 | using Point2 = point<data_t>; | ||
| 12 | using Line2 = line<data_t>; | ||
| 13 | |||
| 14 | 10 | int main() { | |
| 15 | u32 t; | ||
| 16 |
1/2✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
|
10 | cin >> t; |
| 17 |
2/2✓ Branch 0 taken 23 times.
✓ Branch 1 taken 10 times.
|
33 | while (t--) { |
| 18 | u32 n; | ||
| 19 |
1/2✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
|
23 | cin >> n; |
| 20 | Point2 s, target; | ||
| 21 | 23 | cin >> target >> s; | |
| 22 |
1/2✓ Branch 1 taken 23 times.
✗ Branch 2 not taken.
|
23 | vec<Point2> vp(n); |
| 23 |
2/2✓ Branch 6 taken 4636 times.
✓ Branch 7 taken 23 times.
|
4659 | for (auto& p : vp) cin >> p; |
| 24 |
2/2✓ Branch 0 taken 1 time.
✓ Branch 1 taken 22 times.
|
23 | if (!n) { |
| 25 |
1/2✓ Branch 1 taken 1 time.
✗ Branch 2 not taken.
|
1 | cout << "0\n"; |
| 26 | 1 | continue; | |
| 27 | } | ||
| 28 |
1/2✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
|
22 | map<Point2, u32> ids; |
| 29 |
3/4✓ Branch 2 taken 4636 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 4636 times.
✓ Branch 5 taken 22 times.
|
4658 | flt_ (u32, i, 0, n) ids[vp[i]] = i + 1; |
| 30 | 22 | u32 pos = 0; | |
| 31 |
1/2✓ Branch 1 taken 22 times.
✗ Branch 2 not taken.
|
22 | vecb skip(n); |
| 32 | { | ||
| 33 | 22 | data_t len = std::numeric_limits<data_t>::max(); | |
| 34 |
2/2✓ Branch 0 taken 4636 times.
✓ Branch 1 taken 22 times.
|
4658 | flt_ (u32, i, 0, n) { |
| 35 |
3/8✓ Branch 1 taken 4636 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 4636 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 4636 times.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
|
4636 | if (vp[i].x > target.x || vp[i].y > target.y) skip[i] = 1; |
| 36 |
2/2✓ Branch 2 taken 67 times.
✓ Branch 3 taken 4569 times.
|
4636 | if (data_t now = dist_PP(vp[i], s); len > now) len = now, pos = i; |
| 37 | } | ||
| 38 | } | ||
| 39 | 22 | vec<Line2> vl; | |
| 40 |
1/2✓ Branch 3 taken 22 times.
✗ Branch 4 not taken.
|
22 | vl.emplace_back(Point2(0, 0), Point2(target.x, 0)); |
| 41 |
1/2✓ Branch 3 taken 22 times.
✗ Branch 4 not taken.
|
22 | vl.emplace_back(Point2(target.x, 0), Point2(target.x, target.y)); |
| 42 |
1/2✓ Branch 3 taken 22 times.
✗ Branch 4 not taken.
|
22 | vl.emplace_back(Point2(target.x, target.y), Point2(0, target.y)); |
| 43 |
1/2✓ Branch 3 taken 22 times.
✗ Branch 4 not taken.
|
22 | vl.emplace_back(Point2(0, target.y), Point2(0, 0)); |
| 44 | 22 | alist<u32> g(n + 1); | |
| 45 |
2/2✓ Branch 0 taken 4636 times.
✓ Branch 1 taken 22 times.
|
4658 | flt_ (u32, i, 0, n) { |
| 46 |
2/4✓ Branch 1 taken 4636 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 4636 times.
|
4636 | if (skip[i]) continue; |
| 47 |
1/2✓ Branch 1 taken 4636 times.
✗ Branch 2 not taken.
|
4636 | vl.resize(4); |
| 48 |
2/2✓ Branch 0 taken 1715444 times.
✓ Branch 1 taken 4636 times.
|
1720080 | flt_ (u32, j, 0, n) { |
| 49 |
6/8✓ Branch 0 taken 1710808 times.
✓ Branch 1 taken 4636 times.
✓ Branch 3 taken 1710808 times.
✗ Branch 4 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 1710808 times.
✓ Branch 8 taken 4636 times.
✓ Branch 9 taken 1710808 times.
|
1715444 | if (j == i || skip[j]) continue; |
| 50 | 1710808 | Point2 mid = mid_point(vp[i], vp[j]), v = rot90(vp[j] - vp[i]); | |
| 51 |
1/2✓ Branch 2 taken 1710808 times.
✗ Branch 3 not taken.
|
1710808 | vl.emplace_back(mid, mid + v); |
| 52 | } | ||
| 53 |
1/2✓ Branch 1 taken 4636 times.
✗ Branch 2 not taken.
|
4636 | auto res = ins_hPs(vl); |
| 54 |
2/2✓ Branch 1 taken 25527 times.
✓ Branch 2 taken 4636 times.
|
30163 | flt_ (u32, j, 0, res.size()) { |
| 55 | 25527 | Line2 l{res.vs[j], res.vs[res.next(j)]}; | |
| 56 |
1/2✓ Branch 3 taken 25527 times.
✗ Branch 4 not taken.
|
25527 | u32 id = ids[reflect(l, vp[i])]; |
| 57 |
2/2✓ Branch 0 taken 23196 times.
✓ Branch 1 taken 2331 times.
|
25527 | if (id) --id; |
| 58 | 2331 | else id = n; | |
| 59 | 25527 | g.add_arc(i, id, 1); | |
| 60 | 25527 | g.add_arc(id, i, 1); | |
| 61 | } | ||
| 62 | 4636 | } | |
| 63 |
2/4✓ Branch 3 taken 22 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 22 times.
✗ Branch 7 not taken.
|
22 | cout << dijkstra(g, pos, fn_0)[n] << '\n'; |
| 64 |
2/2✓ Branch 5 taken 22 times.
✓ Branch 6 taken 1 time.
|
23 | } |
| 65 | 10 | } | |
| 66 |