CS Academy 050 Div. 2 Check Square

CS Academy 050 Div.2 Check Square

CS Academy

感想

色々やり方がありそうだけど、頂点を見る順番で全探索した。

解法

4点の位置関係がわからないので、その関係を全探索する。順番に点をずらしながら辺を4本とって、その長さがすべて等しくなるような場合が存在するならば正方形になる。実際の距離で考えると誤差が出そうで怖いので距離の二乗で比較する。

実装

#include "bits/stdc++.h"
using namespace std;

int dist(int x1, int y1, int x2, int y2) {
        return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}

void solve() {
        vector<int> x(4), y(4);
        for (int i = 0; i < 4; i ++) cin >> x[i] >> y[i];
        vector<int> ord(4);
        for (int i = 0; i < 4; i ++) ord[i] = i;
        bool ans = false;
        do {
                int a = dist(x[ord[0]], y[ord[0]], x[ord[1]], y[ord[1]]);
                int b = dist(x[ord[1]], y[ord[1]], x[ord[2]], y[ord[2]]);
                int c = dist(x[ord[2]], y[ord[2]], x[ord[3]], y[ord[3]]);
                int d = dist(x[ord[3]], y[ord[3]], x[ord[0]], y[ord[0]]);
                if (a == b && b == c && c == d) ans = true;
        } while (next_permutation(all(ord)));
        cout << ans << endl;
        return;
}

int main() {
        ios::sync_with_stdio(false);
        cin.tie(0);
        int t;
        cin >> t;
        while (t --) solve();
        return 0;
}