test/cpv_local/geo2d/ins_hps.bzoj1038.cpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | // competitive-verifier: LOCALCASE test/cpv_local/_data/bzoj/1038 | ||
| 2 | |||
| 3 | #include "../../../src/geo2d/ins/ll/lib.hpp" | ||
| 4 | #include "../../../src/geo2d/ins_hps/lib.hpp" | ||
| 5 | |||
| 6 | using namespace tifa_libs; | ||
| 7 | using std::cin, std::cout; | ||
| 8 | using data_t = f128; | ||
| 9 | using Point2 = point<data_t>; | ||
| 10 | using Line2 = line<data_t>; | ||
| 11 | using ConvexHull2 = cvh<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 | 10 | set_eps<data_t>(1e-20); | |
| 16 | |||
| 17 | u32 n; | ||
| 18 |
1/2✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
|
10 | cin >> n; |
| 19 |
2/4✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 10 times.
✗ Branch 5 not taken.
|
30 | vec<data_t> x(n), y(n); |
| 20 |
3/4✓ Branch 4 taken 850 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 850 times.
✓ Branch 9 taken 10 times.
|
860 | for (auto& i : x) cin >> i; |
| 21 |
3/4✓ Branch 4 taken 850 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 850 times.
✓ Branch 9 taken 10 times.
|
860 | for (auto& i : y) cin >> i; |
| 22 | 10 | vec<Line2> vl; | |
| 23 |
1/2✓ Branch 3 taken 10 times.
✗ Branch 4 not taken.
|
10 | vl.emplace_back(x.front(), -1e12, x.back(), -1e12); |
| 24 |
1/2✓ Branch 3 taken 10 times.
✗ Branch 4 not taken.
|
10 | vl.emplace_back(x.back(), -1e12, x.back(), 1e12); |
| 25 |
1/2✓ Branch 3 taken 10 times.
✗ Branch 4 not taken.
|
10 | vl.emplace_back(x.back(), 1e12, x.front(), 1e12); |
| 26 |
1/2✓ Branch 3 taken 10 times.
✗ Branch 4 not taken.
|
10 | vl.emplace_back(x.front(), 1e12, x.front(), -1e12); |
| 27 |
3/4✓ Branch 5 taken 840 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 840 times.
✓ Branch 8 taken 10 times.
|
850 | flt_ (u32, i, 0, n - 1) vl.emplace_back(x[i], y[i], x[i + 1], y[i + 1]); |
| 28 |
1/2✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
|
10 | ConvexHull2 cvh = ins_hPs(vl); |
| 29 | 10 | data_t ans = std::numeric_limits<data_t>::max(); | |
| 30 |
1/2✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
|
131 | std::ranges::sort(cvh.vs, [](auto CR lhs, auto CR rhs) { return lhs.x < rhs.x; }); |
| 31 | 10 | u32 i = 0, j = 0; | |
| 32 |
5/6✓ Branch 1 taken 893 times.
✓ Branch 2 taken 10 times.
✓ Branch 3 taken 893 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 893 times.
✓ Branch 6 taken 10 times.
|
903 | while (i < cvh.vs.size() && j < n) { |
| 33 |
8/8✓ Branch 0 taken 883 times.
✓ Branch 1 taken 10 times.
✓ Branch 5 taken 19 times.
✓ Branch 6 taken 864 times.
✓ Branch 10 taken 9 times.
✓ Branch 11 taken 10 times.
✓ Branch 12 taken 9 times.
✓ Branch 13 taken 884 times.
|
893 | if (i && is_eq(cvh[i].x, cvh[i - 1].x) && is_gt(cvh[i].y, cvh[i - 1].y)) { |
| 34 | 9 | ++i; | |
| 35 | 9 | continue; | |
| 36 | } | ||
| 37 |
2/2✓ Branch 3 taken 840 times.
✓ Branch 4 taken 44 times.
|
884 | if (is_gt(cvh[i].x, x[j])) { |
| 38 | 840 | Point2 temp = ins_LL(Line2{cvh[i], cvh[i - 1]}, Line2{Point2{x[j], y[j]}, Point2{x[j], y[j] + 1}}); | |
| 39 | 840 | ans = std::min(ans, abs(temp.y - y[j++])); | |
| 40 | } else { | ||
| 41 |
2/2✓ Branch 0 taken 20 times.
✓ Branch 1 taken 24 times.
|
44 | if (!j) { |
| 42 | 20 | ++i; | |
| 43 | 20 | continue; | |
| 44 | } | ||
| 45 | 24 | Point2 temp = ins_LL(Line2{Point2{x[j - 1], y[j - 1]}, Point2{x[j], y[j]}}, Line2{cvh[i], Point2{cvh[i].x, cvh[i].y + 1}}); | |
| 46 | 24 | ans = std::min(ans, abs(cvh[i++].y - temp.y)); | |
| 47 | } | ||
| 48 | } | ||
| 49 |
2/4✓ Branch 1 taken 10 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 10 times.
✗ Branch 5 not taken.
|
10 | cout << ans << '\n'; |
| 50 | 10 | } | |
| 51 |