C++の練習を兼ねて, AtCoder Beginner Contest 151 の 問題F (Enclose All) を解いてみた.
■感想.
1. 問題Fは, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 二分探索(応用版, 小数点含む) の 復習が出来たので, 非常に良かったと思う.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 151 解説 を ご覧下さい.
■C++版プログラム(問題F／AC版).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
// 解き直し. // https://img.atcoder.jp/abc151/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using P = pair<double, double>; using vp = vector<P>; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) #define pb push_back #define a first #define b second const double EPS = 1e-8; int main(){ // 1. 入力情報. int N; scanf("%d", &N); vp o(N); double xMax = 0.0; double xMin = 1000.0; double yMax = 0.0; double yMin = 1000.0; rep(i, N){ scanf("%lf %lf", &o[i].a, &o[i].b); // 二分探索 の 上限 を 設定する時に利用. xMax = max(xMax, o[i].a); xMin = min(xMin, o[i].a); yMax = max(yMax, o[i].b); yMin = min(yMin, o[i].b); } // 2. 評価関数. auto f = [&](double r) -> bool { // 2-1. 交点を全列挙. vp ps; rep(i, N){ repx(j, i + 1, N){ // 二点間の差分. double dx = o[i].a - o[j].a; double dy = o[i].b - o[j].b; // 交点(二つ)が, 無い場合. if(r * r * 4.0 + EPS - (dx * dx + dy * dy) < 0.0) return false; // 二つの交点間(距離 h). double h = sqrt(r * r * 4.0 - (dx * dx + dy * dy)) / 2.0; // 垂直方向(ベクトル, 二つ). double n = hypot(dx, dy); P v1 = {-dy / n * h, +dx / n * h}; P v2 = {+dy / n * h, -dx / n * h}; // 交点(二つ). double cx = (o[i].a + o[j].a) / 2.0; double cy = (o[i].b + o[j].b) / 2.0; P p1 = {cx + v1.a, cy + v1.b}; P p2 = {cx + v2.a, cy + v2.b}; // 保存. ps.pb(p1); ps.pb(p2); } } // 2-2. 判定. for(auto &p : ps){ // N個の点から, 距離が, R以下のものがいくつあるか？ int res = 0; rep(i, N){ double d2 = (o[i].a - p.a) * (o[i].a - p.a) + (o[i].b - p.b) * (o[i].b - p.b); if(d2 <= r * r + EPS) ++res; } // 判定結果(OK) // -> N個の点からの距離が, いずれも, R以下のものが見つかった. if(res == N) return true; } // 2-3. 判定結果(NG). return false; }; // 3. 二分探索で確認してみる. double l = 0.0, h = hypot(xMax - xMin, yMax - yMin); while(EPS < abs(h - l)){ double m = (h + l) / 2.0; if(f(m)) h = m; else l = m; } // 4. 出力. printf("%.15lf\n", h); return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 |
[入力例] 2 0 0 1 0 [出力例] 0.500000000000000000 ※但し, 上記のプログラムでは, 以下の内容が出力される. 0.500000000000000 [入力例] 3 0 0 0 1 1 0 [出力例] 0.707106781186548 [入力例] 10 10 9 5 9 2 0 0 0 2 7 3 3 2 5 10 0 3 7 1 9 [出力例] 6.726812023536855 [入力例] 3 1 0 2 0 3 0 [出力例] 1.000000000000000 [入力例] 5 8 7 5 3 9 8 10 2 0 7 [出力例] 5.590169945995560 [入力例] 15 65 110 65 61 141 101 101 116 56 107 151 109 91 69 120 99 84 160 147 79 126 83 171 118 130 98 91 169 157 170 [出力例] 71.317950059760392 [入力例] 50 389 163 517 301 405 508 358 278 264 430 470 428 154 510 354 352 73 506 125 506 104 179 160 295 194 380 240 184 490 98 470 22 169 316 117 180 392 436 201 51 240 214 265 462 296 455 137 194 495 217 469 505 195 186 288 104 141 511 276 195 297 156 308 67 180 264 171 466 22 118 31 447 107 378 40 111 141 442 40 445 154 413 248 268 158 24 65 412 217 109 462 427 331 334 281 233 443 414 470 488 [出力例] 312.995606999176516 |
■参照サイト
AtCoder Beginner Contest 151