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

hamayanhamayan's blog

Opposite [AtCoder Beginner Contest 197(Sponsored by Panasonic) D]

https://atcoder.jp/contests/abc197/tasks/abc197_d

前提知識

解説

https://atcoder.jp/contests/abc197/submissions/21324773

幾何問題ではあるが、幾何ライブラリが無くてもギリギリ解けるラインをABCで狙ってきた感じがしますね…

幾何的な考察

これは幾何的な考察をする必要がある。
Nは偶数なので、p0とpN/2の中点を取ることで正N角形の中心が得られる。
正確には、正N角形の全頂点を通る円の中心が得られる。
ここをcenterとしておこう。

centerを中心として考えると、求めたいp1はp0を反時計回りに360/Nだけ回転した座標となる。
よって、今回の問題は

  1. p0-centerをして、centerが中心となるようにp0を平行移動する
  2. 反時計回りに360/Nだけ回転移動させる
  3. centerが元の場所に戻るように+centerをして得られた座標を平行移動する

とすると答えが得られる。

実装

このような幾何問題は競プロではたびたび出てくるので、幾何ライブラリを持っている人が多い。
持っていれば、自分の実装のように実装はやるだけになるのだが、平行移動や回転移動については高校の知識で実装を頑張ってみてほしい。
何を言っているか分からないという人は「アフィン変換」あたりで検索してみるといいと思う。

int N;
P p0, pN2;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    int x, y;
    cin >> x >> y;
    p0 = P(x, y);
    cin >> x >> y;
    pN2 = P(x, y);

    P center = (p0 + pN2) / 2;
    P ans = rotate(p0 - center, 2 * PI / N) + center;

    printf("%0.9f %0.9f\n", real(ans), imag(ans));
}