読者です 読者をやめる 読者になる 読者になる

srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

ABC 022 D - Big Bang

abc 幾何

問題

問題概要

相似比を求める問題

解法

Aの座標に対して行われた操作は平行移動と回転なので、AとBは相似である。よって、相似比を求めれば、よいことなる。どこを見て相似比をみるかは多くの解法があるみたい。 一番簡単なのは、重心からの距離が最大の点に着目して、重心からの距離の比をだせば、それが相似比となり、答えとなる。

ミス

なるほどなーて感じ。

コード

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;

int n;
double ax[100010], ay[100010];
double bx[100010], by[100010];

int main(void){
    cin >> n;
    rep(i, n) cin >> ax[i] >> ay[i];
    rep(i, n) cin >> bx[i] >> by[i];

    //Aの重心を求める
    double agx, agy;
    rep(i, n){
        agx += ax[i];
        agy += ay[i];
    }
    agx /= n; agy /= n;

    //Bの重心を求める
    double bgx, bgy;
    rep(i, n){
        bgx += bx[i];
        bgy += by[i];
    }
    bgx /= n; bgy /= n;

    //Aの重心からもっとも遠い点までの距離の二乗
    double amax = 0;
    rep(i, n){
        amax = max(amax, (ax[i] - agx) * (ax[i] - agx) + (ay[i] - agy) * (ay[i] - agy));
    }
    //Bの重心からもっとも遠い点までの距離の二乗
    double bmax = 0;
    rep(i, n){
        bmax = max(bmax, (bx[i] - bgx) * (bx[i] - bgx) + (by[i] - bgy) * (by[i] - bgy));
    }

    printf("%.7f\n", sqrt(bmax / amax));//比を計算
    return 0;
}