ABC022 D問題 Big Bang

初期点群が与えられ、平行移動、回転、拡大をしたあとの最終点群が与えられたときの拡大率を求める問題。

最近、こういう問題にはこれを考える。こういう問題にはこういうアプローチが多い。みたいに頭の中でカテゴリ化していた自分としてはイレギュラーで、もっと頭を柔らかくするきっかけになった。

最初みたとき、N=1e5なのでまぁO(NlogN)くらいだろうと。二分探索で角度を求めるとかかな？とかよくわからないことを考えていたけど、冷静になって考えれば、これは剛体と一緒で、平行移動や回転をしても変わらないものがあり(重心とか全店対距離の総和とか)、その性質を使えばめちゃめちゃ簡単にとけるということに気づくのにあまりに時間がかかりすぎた。

ということで剛体の重心から最遠点までの距離から拡大率を算出しています。

    int N; cin >> N;
    P A[N], B[N];
    double sumax = 0, sumay = 0;
    double sumbx = 0, sumby = 0;
    for(int i=0; i<N; i++){
        int x, y; cin >> x >> y;
        sumax += x; sumay += y;
        A[i] = P(x,y);
    }
    sumax /= N; sumay /= N;
    double maxa = -1;
    for(int i=0; i<N; i++){
        maxa = max(maxa, square((double)A[i].first-sumax)+square((double)(A[i].second-sumay)));
    }
    for(int i=0; i<N; i++){
        int x, y; cin >> x >> y;
        sumbx += x; sumby += y;
        B[i] = P(x,y);
    }
    sumbx /= N; sumby /= N;
    double maxb = -1;
    for(int i=0; i<N; i++){
        maxb = max(maxb, square((double)B[i].first-sumbx)+square((double)(B[i].second-sumby)));
    }
    printf("%14.14f\n", sqrt(maxb/maxa));