ABC108 B問題 : Ruined Square - 忘れても大丈夫

問題. Ruined Square

平面上に正方形があり，頂点は時計回りに $p_1, p_2, p_3, p_4$ である． $p_1, p_2$ が与えられたときに $p_3, p_4$ を答えよ．

ベクトル $v = (x, y)$ と 2次元正方行列 $R(\theta) = \left(\begin{array}{cc} \cos(\theta) & -\sin(\theta) \\ \sin(\theta) & \cos(\theta) \end{array}\right)$ に対して， $R(\theta) v$ は $v$ を原点中心の半時計回りに $\theta$ 回転したベクトルとなる． $R(\theta)$ は回転行列と呼ばれている．今回の問題では正方形の内角である $R(\pi / 2)$ の計算が必要となり，
　 $R(\pi / 2)v = \left(\begin{array}{cc} 0 & -1 \\ 1 & 0 \end{array} \right) \left( \begin{array}{c} x \\ y \end{array} \right) = \left(\begin{array}{c} -y \\ x\end{array}\right)$
となる．
よって，頂点 $p_i = (x_i, y_i)\, (i = 1, 2, 3, 4)$ は回転行列を用いて，
　 $p_i = R(\pi / 2) (p_{i - 1} - p_{i - 2}) + p_{i-1} = (x_{i - 1} - y_{i - 1} + y_{i - 2}, x_{i - 1} - x_{i - 2} + y_{i - 1})$
となる．
ちなみに， $p_1, p_2$ が整数点ならば上の式から $p_2, p_3$ も整数点である．

計算時間： $O(1)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

struct Point {
    int x, y;
    Point(int _x, int _y) : x(_x), y(_y) {}
    Point() {}
    Point operator+(const Point &rhs) {
        return Point(this->x + rhs.x, this->y + rhs.y);
    }
    Point operator-(const Point &rhs) {
        return Point(this->x - rhs.x, this->y - rhs.y);
    }
};
inline Point Rotate90(const Point &p) {
    return Point(-p.y, p.x);
}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    vector<Point> p(4);
    for (int i = 0; i < 2; ++i)
        cin >> p[i].x >> p[i].y;

    for (int i = 2; i < 4; ++i)
        p[i] = Rotate90(p[i - 1] - p[i - 2]) + p[i - 1];

    for (int i = 2; i < 4; ++i)
        cout << p[i].x << ' ' << p[i].y << (i == 3 ? '\n' : ' ');

    return 0;
}

まとめ

軸並行な正方形と勘違いしていた．

問題. Ruined Square

解法. 回転行列

まとめ