Facebook Hacker Cup 2016 Qualification Round Boomerang Constellations

問題

https://www.facebook.com/hackercup/problem/910374079035613/

解法

点 A, B, C で AB = AC となるときの頂点 A について全探索します。
頂点 A からの他の頂点への距離を全部調べてソートすると, 例えば距離のリストとして 3, 3, 4, 4, 4 となったとすると, 距離 3 になって等しくなる頂点の組み合わせは 2C2 個あって, 距離 4 になって等しくなる頂点の組み合わせは 3C2 個あります。こんな感じで, 一般にある頂点から n 個距離が等しくなる頂点があったら, それらを使って nC2 通りのペアが作れます。

この解法は O(n^2 log n) でできるので, 時間内に答えを求められます。

ですが, すこし懸念なのは, AB = AC = BC となる点 A, B, C があった場合, 重複して 3 つの頂点の組を数えてしまう可能性があることです。ですが, このようなことは起こりえません。なぜなら, AB = AC = BC となるとき三角形 ABC は正三角形になり, AC ベクトルは AC ベクトルを 60 度回転したものになりますが, どちらも整数になるとすると sqrt(3) が有理数になるというよくあるアレが導かれて矛盾します。よって, AB = AC = BC となるような頂点の組は存在しません。

int X[2222], Y[2222];

ll square(ll x) {return x*x;}

void solve(int T) {
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> X[i] >> Y[i];
    }
    ll ans = 0;
    for (int i = 0; i < N; i++) {
        vector<ll> v(N);
        for (int j = 0; j < N; j++) {
            v[j] = (square(X[i]-X[j]) + square(Y[i]-Y[j]));
        }
        sort(v.begin(), v.end());
        int cur = 0;
        while (cur < N) {
            int i = cur;
            while (i < N && v[cur] == v[i]) i++;
            ll cnt = i-cur;
            ans += cnt*(cnt-1)/2;
            cur = i;
        }
    }
    cout << "Case #" << T << ": " << ans << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int T;
    cin >> T;
    for (int t = 1; t <= T; t++) {
        solve(t);
    }
    return 0;
}