mayoko’s diary

プロコンとかいろいろ。

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;
}