C++の練習を兼ねて, AtCoder Beginner Contest 022 の 問題D (D – Big Bang) を解いてみた.
■感想.
1. 重心から, 最も近い点を考慮して, 拡大率を求める方針で実装したが, AC版を取れなかった.
※ 解説を見たところ, 距離が, 0 になる場合があって, 場合分けが必要との指摘があった.
※ 途中, redeclared as different kind of symbol の error も 出てきて, 実装に手こずってしまった.
2. 解説にある方法の中で, 重心から, 最も遠い点を考慮する方針に変更したら, AC版となった.
3. 時間を見つけて, 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 022解説をご覧下さい.
■C++版プログラム(問題D／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 |
// 解き直し. // https://www.slideshare.net/chokudai/abc022 #include <bits/stdc++.h> using namespace std; #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--) const double INF = 202020202020.0; const int MAX = 101010; // ./Main.cpp:10:14: error: ‘double y1 [101010]’ redeclared as different kind of symbol double ax1[MAX], ay1[MAX], ax2[MAX], ay2[MAX]; int main(){ // 1. 入力情報. int N; scanf("%d", &N); // 2. 1回目の観測. double gx1 = 0.0, gy1 = 0.0, gx2 = 0.0, gy2 = 0.0; rep(i, N){ scanf("%lf %lf", &ax1[i], &ay1[i]); gx1 += ax1[i]; gy1 += ay1[i]; } // 3. 2回目の観測. rep(i, N){ scanf("%lf %lf", &ax2[i], &ay2[i]); gx2 += ax2[i]; gy2 += ay2[i]; } // 4. 重心を計算. gx1 /= (double)N, gy1 /= (double)N; gx2 /= (double)N, gy2 /= (double)N; // 5. 重心から一番遠い点の距離を計算. double d1 = 0.0, d2 = 0.0; rep(i, N) d1 = max(d1, hypot(ax1[i] - gx1, ay1[i] - gy1)); rep(i, N) d2 = max(d2, hypot(ax2[i] - gx2, ay2[i] - gy2)); // 6. 拡大率を計算. double ans = d2 / d1; // 7. 出力. printf("%.12lf\n", ans); 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 |
[入力例] 4 0 0 0 1 1 0 1 1 0 2 2 0 -2 0 0 -2 [出力例] 2.8284271247 ※AtCoderテストケースより 但し, 上記のプログラムでは, 以下の内容が出力される. 2.828427124746 [入力例] 6 3 4 1 3 4 3 2 2 0 1 2 0 5 5 -1 2 -1 -3 2 1 2 6 4 -3 [出力例] 2.2360679775 ※AtCoderテストケースより 但し, 上記のプログラムでは, 以下の内容が出力される. 2.236067977500 |
■参照サイト
AtCoder Beginner Contest 022