問題概要

二次元の座標平面上に $N$ 個の点がある。点 $i$ の座標は $(x_{i}, y_{i}$ である。

これら $N$ 個の点から 4 個を選ぶ。選んだ 4 点が正方形の頂点となる場合についての、正方形の面積の最大値を答えよ。

制約

$1 \le N \le 3000$
$0 \le x_{i}, y_{i} \le 5000$

考えたこと

$N \le 3$ であるような入力もあるようだが、その場合は答えは 0 だということでよさそうだ。 $N \ge 4$ であるとしよう。

まず素朴な解法として、 $N$ 点から 4 点を選ぶ方法をすべて調べる方法が考えられる。4 点が正方形がなすかどうかを判定し、正方形ならばその面積の最大値を求めれば良い。ただし、この解法では $O(N^{4})$ の計算量を要する。このままでは満点は取れないので高速化したい。

ここで、 $N$ 個の点のうち、2 個 $P, Q$ を選べば、その 2 点 $P, Q$ を含む正方形は次の図のような 2 通りのいずれかに決まることに注意しよう！

これら 2 つの正方形について、次の処理を行えばよい。

2 点以外の 2 点が、与えられた点に含まれるかどうかを判定する
- あらかじめ、点 $(p, q)$ が $N$ 点に含まれるかどうかを表す bool 配列を用意しておくとよい
含まれるならば、この正方形の面積の最大値を求める

この解法であれば、計算量は $O(N^{2})$ となって間に合う。

コード

#include <bits/stdc++.h>
using namespace std;
const int MAX = 5100;

int main() {
    vector isin(MAX, vector(MAX, false));
    int N;
    cin >> N;
    vector<int> x(N), y(N);
    for (int i = 0; i < N; i++) {
        cin >> x[i] >> y[i];
        isin[x[i]][y[i]] = true;
    }

    // 点 (p, q) が N 点に含まれるかどうか
    auto check = [&](int p, int q) -> bool {
        if (p < 0 || p >= MAX || q < 0 || q >= MAX) return false;
        return isin[p][q];
    };

    // 2 点を試していく
    int res = 0;
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            int x1 = x[i], y1 = y[i], x2 = x[j], y2 = y[j];
            int dx = x2 - x1, dy = y2 - y1;
            int square = dx * dx + dy * dy;

            // i を中心として i->j を 90 度回転した点を考える
            {
                int x3 = x1 - dy, y3 = y1 + dx;
                int x4 = x2 + x3 - x1, y4 = y2 + y3 - y1;
                if (check(x3, y3) && check(x4, y4)) {
                    res = max(res, square);
                }
            }

            // i を中心として i->j を -90 度回転した点を考える
            {
                int x3 = x1 + dy, y3 = y1 - dx;
                int x4 = x2 + x3 - x1, y4 = y2 + y3 - y1;
                if (check(x3, y3) && check(x4, y4)) {
                    res = max(res, square);
                }
            }
        }
    }
    cout << res << endl;
}