test/cpv_local/geo2d/ins_ll.bzoj1091.cpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | // competitive-verifier: LOCALCASE test/cpv_local/_data/bzoj/1091 | ||
| 2 | |||
| 3 | #include "../../../src/geo2d/dis/pp/lib.hpp" | ||
| 4 | #include "../../../src/geo2d/ins/ll/lib.hpp" | ||
| 5 | #include "../../../src/io/container/lib.hpp" | ||
| 6 | |||
| 7 | using namespace tifa_libs; | ||
| 8 | using std::cin, std::cout; | ||
| 9 | using data_t = f64; | ||
| 10 | using Point2 = point<data_t>; | ||
| 11 | using Line2 = line<data_t>; | ||
| 12 | |||
| 13 | 10 | int main() { | |
| 14 |
1/2✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
|
10 | cout << std::fixed << std::setprecision(3); |
| 15 | |||
| 16 | u32 n, m; | ||
| 17 |
2/4✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 10 times.
✗ Branch 5 not taken.
|
10 | cin >> n >> m; |
| 18 | 10 | vec<Line2> vl; | |
| 19 |
1/2✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
|
10 | vl.emplace_back(0, 0, n, 0); |
| 20 |
1/2✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
|
10 | vl.emplace_back(n, 0, n, m); |
| 21 |
1/2✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
|
10 | vl.emplace_back(n, m, 0, m); |
| 22 |
1/2✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
|
10 | vl.emplace_back(0, m, 0, 0); |
| 23 | u32 p; | ||
| 24 |
1/2✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
|
10 | cin >> p; |
| 25 |
1/2✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
|
10 | vec<Point2> vp(p); |
| 26 | 10 | cin >> vp; | |
| 27 |
1/2✓ Branch 3 taken 10 times.
✗ Branch 4 not taken.
|
10 | vl.emplace_back(vp[0], vp[p - 1]); |
| 28 |
3/4✓ Branch 3 taken 42 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 42 times.
✓ Branch 6 taken 10 times.
|
52 | flt_ (u32, i, 0, p - 1) vl.emplace_back(vp[i + 1], vp[i]); |
| 29 |
1/2✓ Branch 4 taken 10 times.
✗ Branch 5 not taken.
|
10 | std::sort(begin(vl) + 4, end(vl)); |
| 30 | 10 | data_t ans = std::numeric_limits<data_t>::max(); | |
| 31 | 10 | Point2 INFP{1e5, 1e5}; | |
| 32 | do { | ||
| 33 | 82962 | data_t now_ans = 0; | |
| 34 |
2/2✓ Branch 1 taken 658830 times.
✓ Branch 2 taken 82962 times.
|
741792 | flt_ (u32, i, 4, (u32)vl.size()) { |
| 35 | 658830 | Point2 l = INFP, r = INFP; | |
| 36 |
2/2✓ Branch 0 taken 4927038 times.
✓ Branch 1 taken 658830 times.
|
5585868 | flt_ (u32, j, 0, i) { |
| 37 |
2/2✓ Branch 3 taken 128232 times.
✓ Branch 4 taken 4798806 times.
|
6817662 | if (!is_ins_LL(vl[i], vl[j])) continue; |
| 38 | 4798806 | Point2 p = ins_LL(vl[i], vl[j]); | |
| 39 |
8/8✓ Branch 0 taken 4387734 times.
✓ Branch 1 taken 411072 times.
✓ Branch 2 taken 3607422 times.
✓ Branch 3 taken 780312 times.
✓ Branch 4 taken 3279408 times.
✓ Branch 5 taken 328014 times.
✓ Branch 6 taken 371226 times.
✓ Branch 7 taken 2908182 times.
|
4798806 | if (p.x < 0 || p.y < 0 || p.x > n || p.y > m) continue; |
| 40 |
6/6✓ Branch 5 taken 1454091 times.
✓ Branch 6 taken 1454091 times.
✓ Branch 12 taken 1205397 times.
✓ Branch 13 taken 248694 times.
✓ Branch 14 taken 1205397 times.
✓ Branch 15 taken 1702785 times.
|
2908182 | if (!is_lt(dist_PP(vl[i].l, p), dist_PP(vl[i].r, p)) && is_lt(dist_PP(vl[i].l, p), dist_PP(vl[i].l, l))) l = p; |
| 41 |
6/6✓ Branch 5 taken 1454091 times.
✓ Branch 6 taken 1454091 times.
✓ Branch 12 taken 1205397 times.
✓ Branch 13 taken 248694 times.
✓ Branch 14 taken 1205397 times.
✓ Branch 15 taken 1702785 times.
|
2908182 | if (!is_lt(dist_PP(vl[i].r, p), dist_PP(vl[i].l, p)) && is_lt(dist_PP(vl[i].r, p), dist_PP(vl[i].r, r))) r = p; |
| 42 | } | ||
| 43 | 658830 | now_ans += dist_PP(l, r); | |
| 44 | } | ||
| 45 | 82962 | ans = std::min(ans, now_ans); | |
| 46 |
3/4✓ Branch 4 taken 82962 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 82952 times.
✓ Branch 7 taken 10 times.
|
82962 | } while (std::next_permutation(begin(vl) + 4, end(vl))); |
| 47 |
2/4✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 10 times.
✗ Branch 5 not taken.
|
10 | cout << ans << '\n'; |
| 48 | 10 | } | |
| 49 |