はまやんはまやんはまやん

hamayanhamayan's blog

Congruence Points [AtCoder Beginner Contest 207 D]

競技プログラミング

https://atcoder.jp/contests/abc207/tasks/abc207_d

前提知識

解説

https://atcoder.jp/contests/abc207/submissions/23804855

微妙に幾何知識が必要。
自分の解法は想定解法ではなく、かつ、コンパイル時最適化でTLEをごり消した解法です。
慣れずに通すのは難しいと思うので、こういう解法もあります程度に見るといいです。
公式解法の重心を使う方針の方が、凸包とかでも使えて汎用的でオススメです…

何から始めるか

全探索できそうな所を一通り考えていく。
制約から解法を考えていくと、とりあえずどの点とどの点が対応しているかを1組は全探索できそうである。
1組対応する点が決まれば、各点の集合をその点を中心に変更移動させて、あとは片方を適当に回転させて一致するかを確認すればよくなる。
つまり、平行移動について考える必要がなくなるのがいい所。
あとは回転させて一致するかの判定問題となった。

回転させて一致するか

ただ単に回転といっても回転は実数なので、回転角度を全探索する方針は難しい。
よってある程度回転角度を絞って確認する必要がある。

点の集合Tについて中心として選んだ点以外に1つ点を選択して、その点が回転後にどうなるかについて考えてみる。
答えとなる回転角度は少なくとも適当に選んだ1つのその点の移動先が格子上（xy座標どちらも整数）に移る必要がある。
この回転によって移動可能な格子上の点はそれほど多くなく、というかかなり少なく、全探索しても問題無さそうな雰囲気がある。
なので、候補の回転角については、適当に選んだ1つの点が回転によって格子上の点に移動するものを利用する。

候補の回転角を探すには遷移先の格子上の点を全探索して、「中心からの距離が等しい」ならば回転によって移動可能であると判断する方法を取る。
今回は[-10,10]の範囲に点が与えられているので中心で平行移動しても[-20,20]の範囲に点が収まることになる。
よって、xy座標について[-20,20]を全探索して中心からの距離が、適当に選んだ1つの点と等しくなる点を探すことで回転によって移動可能な点を探す。

回転によって移動可能な点が分かれば、「回転によって移動可能な点」と「中心」と「適当に選んだ1つの点」の角度を調べれば回転角を求めることができる。
実装ではthreePointArgumentTokei関数として自分は用意している。

回転角が分かったら…

回転角が分かったら、あとは、点集合Tについてその回転をすべて適用して、点集合Sと一致するか確認する。
確認方法は、回転後の2つの集合を普通にソートして、ソート後に先頭から順に点が一致するかを判定していく方式を取る。
正直ここがかなり嘘解法っぽいんだけれど、集合が仮に一致していた場合、ソートをしたら同じようにソートされるはずで理論的には正しく判定されるとは思うんだけれど、
doubleで値を持っているので、誤差でソートが壊れるということは大いに考えられたが、出したら大丈夫だった。

これで完全に一致していたらYesで答えるし、すべての場合でダメだったらNo

実装について

小数比較について

「中心からの距離が等しい」というのを判定するのにlen == len2みたいな比較をしたくなるが、こういう場合はabs(len - len2) < EPSとすると誤差を吸収できる。
あと、2点が一致するという部分も2点間の距離がゼロという風に変換をしてabs(X - Y) == 0として、誤差を考慮してabs(X - Y) < EPSと言う風にして誤差を吸収する。

間に合う？

実際テンプレで長らく使ってなかった#pragma GCC optimize ("-O3")を使って最適化させてTLEを回避した。
O(N3logN|回転角候補最大数|)
みたいな感じになるから相当ギリギリ。

int N; P ps[101], pt[101], pt2[101];
//---------------------------------------------------------------------------------------------------
#define yes "Yes"
#define no "No"
string solve() {
    if (N == 1) return yes;

    rep(centerS, 0, N) rep(centerT, 0, N) {
        rep(k, 0, N) if (centerS != k) ps[k] -= ps[centerS];
        ps[centerS] = P(0, 0);

        rep(k, 0, N) if (centerT != k) pt[k] -= pt[centerT];
        pt[centerT] = P(0, 0);

        int t = (centerT == 0) ? 1 : 0;
        double len = abs(pt[centerT] - pt[t]);
        
        vector<double> rots;
        rep(x, -20, 21) rep(y, -20, 21) {
            P p(x, y);
            double len2 = abs(p);
            if (abs(len - len2) < EPS) rots.push_back(threePointArgumentTokei(p, pt[centerT], pt[t]));
        }

        fore(rot, rots) {
            rep(k, 0, N) pt2[k] = rotate(pt[k], rot);

            sort(ps, ps + N);
            sort(pt2, pt2 + N);

            bool ok = true;
            rep(k, 0, N) if (EPS < abs(pt2[k] - ps[k])) ok = false;
            if (ok) return yes;
        }
    }

    return no;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) {
        int a, b; cin >> a >> b;
        ps[i] = P(a, b);
    }
    rep(i, 0, N) {
        int a, b; cin >> a >> b;
        pt[i] = P(a, b);
    }
    cout << solve() << endl;
}