test/cpv_local/geo2d/tcenter_o.cf274c.cpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | // competitive-verifier: LOCALCASE test/cpv_local/_data/codeforces/274C | ||
| 2 | // competitive-verifier: ERROR 0.0001 | ||
| 3 | |||
| 4 | #include "../../../src/geo2d/ds/c/lib.hpp" | ||
| 5 | #include "../../../src/geo2d/pred/is_on_same_l/lib.hpp" | ||
| 6 | #include "../../../src/geo2d/proj/lib.hpp" | ||
| 7 | #include "../../../src/geo2d/tcenter/o/lib.hpp" | ||
| 8 | |||
| 9 | using namespace tifa_libs; | ||
| 10 | using std::cin, std::cout; | ||
| 11 | using data_t = f64; | ||
| 12 | using Point2 = point<data_t>; | ||
| 13 | using Circle2 = circle<data_t>; | ||
| 14 | using Triangle2 = triangle<data_t>; | ||
| 15 | |||
| 16 | 21 | int main() { | |
| 17 |
1/2✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
|
21 | cout << std::fixed << std::setprecision(20); |
| 18 | |||
| 19 | 21 | set_eps<data_t>(1e-9); | |
| 20 | u32 n; | ||
| 21 |
1/2✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
|
21 | cin >> n; |
| 22 |
1/2✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
|
21 | set<Point2> exists; |
| 23 | 21 | vec<Point2> vp; | |
| 24 |
1/2✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
|
21 | vp.reserve(n); |
| 25 | data_t x, y; | ||
| 26 |
2/2✓ Branch 0 taken 282 times.
✓ Branch 1 taken 21 times.
|
303 | for (u32 i = 1; i <= n; ++i) { |
| 27 |
2/4✓ Branch 1 taken 282 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 282 times.
✗ Branch 5 not taken.
|
282 | cin >> x >> y; |
| 28 |
1/2✓ Branch 2 taken 282 times.
✗ Branch 3 not taken.
|
282 | exists.insert(Point2{x, y}); |
| 29 |
1/2✓ Branch 1 taken 282 times.
✗ Branch 2 not taken.
|
282 | vp.emplace_back(x, y); |
| 30 | } | ||
| 31 | struct Comp { | ||
| 32 |
2/2✓ Branch 1 taken 62270 times.
✓ Branch 2 taken 619948 times.
|
682218 | bool operator()(const Circle2& lhs, const Circle2& rhs) const { retif_((lhs.o == rhs.o), lhs.r < rhs.r, lhs.o < rhs.o); } |
| 33 | }; | ||
| 34 |
1/2✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
|
21 | set<Circle2, Comp> circles; |
| 35 |
2/2✓ Branch 0 taken 282 times.
✓ Branch 1 taken 21 times.
|
303 | flt_ (u32, i, 0, n) |
| 36 |
2/2✓ Branch 0 taken 6798 times.
✓ Branch 1 taken 282 times.
|
7080 | flt_ (u32, j, i + 1, n) |
| 37 |
2/2✓ Branch 0 taken 179307 times.
✓ Branch 1 taken 6798 times.
|
186105 | flt_ (u32, k, j + 1, n) { |
| 38 |
2/2✓ Branch 4 taken 4611 times.
✓ Branch 5 taken 174696 times.
|
307026 | if (is_on_same_L(vp[i], vp[j], vp[k])) continue; |
| 39 | 174696 | Triangle2 t{vp[i], vp[j], vp[k]}; | |
| 40 |
2/2✓ Branch 1 taken 115769 times.
✓ Branch 2 taken 58927 times.
|
174696 | if (t.is_obtuse()) continue; |
| 41 |
2/2✓ Branch 1 taken 15958 times.
✓ Branch 2 taken 42969 times.
|
58927 | if (t.is_right()) { |
| 42 |
8/10✓ Branch 5 taken 5499 times.
✓ Branch 6 taken 10459 times.
✓ Branch 8 taken 5499 times.
✗ Branch 9 not taken.
✓ Branch 16 taken 5499 times.
✗ Branch 17 not taken.
✓ Branch 19 taken 4161 times.
✓ Branch 20 taken 1338 times.
✓ Branch 21 taken 4161 times.
✓ Branch 22 taken 11797 times.
|
15958 | if (is_zero(dot(vp[i], vp[j], vp[k])) && exists.find(reflect({vp[j], vp[k]}, vp[i])) == end(exists)) continue; |
| 43 |
8/10✓ Branch 5 taken 5178 times.
✓ Branch 6 taken 6619 times.
✓ Branch 8 taken 5178 times.
✗ Branch 9 not taken.
✓ Branch 16 taken 5178 times.
✗ Branch 17 not taken.
✓ Branch 19 taken 3835 times.
✓ Branch 20 taken 1343 times.
✓ Branch 21 taken 3835 times.
✓ Branch 22 taken 7962 times.
|
11797 | if (is_zero(dot(vp[j], vp[k], vp[i])) && exists.find(reflect({vp[k], vp[i]}, vp[j])) == end(exists)) continue; |
| 44 |
8/10✓ Branch 5 taken 5281 times.
✓ Branch 6 taken 2681 times.
✓ Branch 8 taken 5281 times.
✗ Branch 9 not taken.
✓ Branch 16 taken 5281 times.
✗ Branch 17 not taken.
✓ Branch 19 taken 3954 times.
✓ Branch 20 taken 1327 times.
✓ Branch 21 taken 3954 times.
✓ Branch 22 taken 4008 times.
|
7962 | if (is_zero(dot(vp[k], vp[i], vp[j])) && exists.find(reflect({vp[i], vp[j]}, vp[k])) == end(exists)) continue; |
| 45 | } | ||
| 46 |
1/2✓ Branch 4 taken 46977 times.
✗ Branch 5 not taken.
|
46977 | circles.insert(Circle2{center_O(t), radius_O(t)}); |
| 47 | } | ||
| 48 | 21 | data_t ans = -1; | |
| 49 |
5/8✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 21 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 37062 times.
✗ Branch 9 not taken.
✓ Branch 11 taken 37062 times.
✓ Branch 12 taken 21 times.
|
74145 | for (auto [o, r] : circles) { |
| 50 | 37062 | bool f = 0; | |
| 51 |
2/2✓ Branch 5 taken 117652 times.
✓ Branch 6 taken 165 times.
|
117817 | for (auto CR p : vp) |
| 52 |
2/2✓ Branch 2 taken 36897 times.
✓ Branch 3 taken 80755 times.
|
117652 | if ((f |= is_lt(dist_PP(p, o), r))) break; |
| 53 |
2/2✓ Branch 0 taken 36897 times.
✓ Branch 1 taken 165 times.
|
37062 | if (f) continue; |
| 54 | 165 | ans = std::max(ans, r); | |
| 55 | } | ||
| 56 |
2/2✓ Branch 0 taken 9 times.
✓ Branch 1 taken 12 times.
|
21 | if (ans < 0) ans = -1; |
| 57 |
2/4✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 21 times.
✗ Branch 5 not taken.
|
21 | cout << ans << '\n'; |
| 58 | 21 | } | |
| 59 |