ABC 022 D - Big Bang
問題概要
相似比を求める問題
解法
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; }