正方形判定
4 点の座標が与えられたとき、それらが正方形を成すか判定する方法。
http://codeforces.com/contest/474/problem/C で必要になった。
4 点間の距離を 4C2=6 通り計算し、それらの比が 1:1:1:1:√2:√2 になっていればよい。
ルートを取ると誤差が怖いので、実際には距離の自乗の比が 1:1:1:1:2:2 になっているか確認する。
ただし、すべての距離が 0 になる場合に注意。
このとき正方形は潰れてしまっているので、適宜処理しなければならない。
以下コード例。int 型の桁あふれに注意。
bool check(vector<int>& x, vector<int>& y) { vector<int> v; for (int i = 0; i < 4; i++) for (int j = i + 1; j < 4; j++) { int dx = x[i] - x[j], dy = y[i] - y[j]; v.push_back(dx * dx + dy * dy); } sort(v.begin(), v.end()); int l = v[0]; if (l == 0) return false; // 点が重なる return v[0]==l && v[1]==l && v[2]==l && v[3]==l && v[4]==l*2 && v[5]==l*2; }
同様に立方体判定もできる。
bool check(vector<int>& x, vector<int>& y, vector<int>& z) { vector<int> v; for (int i = 0; i < 8; i++) for (int j = i + 1; j < 8; j++) { int dx = x[i] - x[j], dy = y[i] - y[j], dz = z[i] - z[j]; v.push_back(dx * dx + dy * dy + dz * dz); } sort(v.begin(), v.end()); int l = v[0]; if (l == 0) return false; // 点が重なる return v[0]==l && v[11]==l && v[12]==l*2 && v[23]==l*2 && v[24]==l*3 && v[27]==l*3; }