ABC #022 D - Big Bang
問題:D: Big Bang - AtCoder Beginner Contest 022 | AtCoder
解法:問題のような変換をしても重心から最遠点までの距離の比はPのままであるのでそれを計算して比べる。
以下ソースコード
const int MAXN = 100100; int Ax[MAXN], Ay[MAXN], Bx[MAXN], By[MAXN]; double square(double x) {return x*x;} double dist(double x1, double y1, double x2, double y2) { return sqrt(square(x2-x1) + square(y2-y1)); } int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; double ax, ay, bx, by; for (int i = 0; i < N; i++) { cin >> Ax[i] >> Ay[i]; ax += Ax[i]; ay += Ay[i]; } ax /= N; ay /= N; for (int i = 0; i < N; i++) { cin >> Bx[i] >> By[i]; bx += Bx[i]; by += By[i]; } bx /= N; by /= N; double da = 0, db = 0; for (int i = 0; i < N; i++) { da = max(da, dist(ax, ay, 1.*Ax[i], 1.*Ay[i])); db = max(db, dist(bx, by, 1.*Bx[i], 1.*By[i])); } double P = db/da; printf("%.15lf\n", P); return 0; }