Nevus [第七回 アルゴリズム実技検定 I]

https://atcoder.jp/contests/past202107-open/tasks/past202107_i

前提知識

• 幾何問題

解説

https://atcoder.jp/contests/past202107-open/submissions/24478121

幾何問題である。複素数を使って座標を保持しながら、幾何的な操作を行っていくのがいい。
幾何問題はその場でのライブラリ整備はだいぶきついので、ライブラリを作っておく必要がある。
書き下してみると、今回必要となる要素結構多いですね…

• 座標保持
• 中点計算
• 平行移動
• 中心からの距離
• 回転角の計算
• 回転操作

平行移動と回転操作

2つ合わさってくると、複雑なので、どちらかを先に行ってしまって、あとは片方だけというのが理想である。
今回はこの理想を実現することができる。

移動前の頂点についての情報は何一つ分かっていないのだが、実は1つ特徴的な点を作り出すことができる。
それが、目と目の中点である。
移動前の目と目の中点は原点となっているので、移動後の目と目の中点を原点に合わせてやれば、
平行移動を行うことができる。

よって、最初に移動後の目と目の中点を計算し、それが原点になるように平行移動をしておく。
複素数で座標を持っていれば、平行移動はベクトルの加減算なので、中心の座標を全部から引いてやればいい。
これでだいぶ楽になった。

回転移動…の前に

回転移動を次は考えるが、どれだけ回転したかを考えるには、基準となる2つの点を用意する必要がある。
依然として、移動前の座標は何一つ分かっていないように見えるが、実は、平行移動によってEが計算できるようになっている。

開店前の目は原点からの距離がEであるが、原点を中心とした回転移動では距離は変わらないので、
平行移動後の目と原点との距離はEになっていることが分かる。
これでEが求められると移動前の右目の座標(-E,0)が分かるので、移動後と比べてみるとどれだけ回転しているかが
計算可能になった。

回転移動

後は回転角を求めて、すべてのほくろをそれで回転させると答えが得られる。
自分の実装では原点を中心として、移動後の右目の位置から移動前の右目の位置(-E,0)への回転角を求めて、
それを全部のほくろに適用している。
ライブラリが整備されていればこの辺はそれほど難しくない。
///////////////////////// writeup2 end *

int N;
vector<P> eyes, dots;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, 2) {
        int x, y; cin >> x >> y;
        eyes.push_back(P(x, y));
    }
    rep(i, 0, N) {
        int x, y; cin >> x >> y;
        dots.push_back(P(x, y));
    }

    // 平行移動
    P center = (eyes[0] + eyes[1]) / 2;
    rep(i, 0, 2) eyes[i] -= center;
    rep(i, 0, N) dots[i] -= center;

    double E = abs(eyes[0]);

    // 回転移動
    double rad = argumentAntiClockwise(P(0, 0), eyes[0], P(-E, 0));
    rep(i, 0, N) {
        P ans = rotate(dots[i], rad);
        printf("%.10f %.10f\n", real(ans), imag(ans));
    }
}