C++でx軸・y軸に平行な正方形を形成する4点を見つけるアルゴリズム

与えられた n 組の点の中から、辺が x 軸と y 軸に平行な正方形を構成する4点を見つけ出すのが本稿のテーマです。条件を満たす正方形が存在しない場合は「No such square」と表示します。また、候補となる正方形が複数存在する場合は面積が最大のものを選択しなければならない点に注意してください。

入力例

n = 6, points = (2, 2), (5, 5), (4, 5), (5, 4), (2, 5), (5, 2)

出力例

Side of the square is: 3,
points of the square are 2, 2 5, 2 2, 5 5, 5

解説

(2, 2)、(5, 2)、(2, 5)、(5, 5) の4点は、一辺の長さが3の正方形を形作ります。

入力例（正方形が存在しないケース）

n = 6, points = (2, 2), (5, 6), (4, 5), (5, 4), (8, 5), (4, 2)

出力例

No such square

解法アプローチ

1. 単純な方法（全探索）

4つのネストしたループですべての点の組み合わせを列挙し、選んだ4点が座標軸に平行な正方形を形成するかどうかを検証します。正方形が成立した場合は、それまでに見つかった正方形よりも面積が大きいかどうかを確認し、条件を満たしていれば結果として保存します。プログラムの最後に保存しておいた結果を出力します。

時間計算量：O(N⁴)

2. 効率的な方法

正方形の対角となる2点（左下と右上）を選ぶための二重ループを構築します。この2点から正方形を生成し、残りの2点が点集合の中に実際に存在するかどうかを確認します。

点の存在判定を高速化するため、あらかじめすべての点をマップ（連想配列）に格納しておくことで、存在確認にかかる時間を大幅に削減できます。同時に、これまでに発見した中で最大の正方形を面積基準で管理し、最終的にその結果を表示します。

時間計算量：O(N² log N)

C++による実装例

// 上記アプローチのC++実装
#include <bits/stdc++.h>
using namespace std;

// 最大の正方形を求める関数
void findLargestSquare1(long long int points1[][2], int n1) {
    // 存在する点を記録するマップ
    map<pair<long long int, long long int>, int> m1;

    // 利用可能な点をマーク
    for (int i = 0; i < n1; i++) {
        m1[make_pair(points1[i][0], points1[i][1])]++;
    }

    long long int side1 = -1, x1 = -1, y1 = -1;

    // 正方形の対角頂点を選ぶための二重ループ
    for (int i = 0; i < n1; i++) {
        // 選択した点を一時的に削除
        m1[make_pair(points1[i][0], points1[i][1])]--;

        for (int j = 0; j < n1; j++) {
            // 選択した点を一時的に削除
            m1[make_pair(points1[j][0], points1[j][1])]--;

            // 残りの2点が存在するかどうかを確認
            if (i != j && (points1[i][0] - points1[j][0]) == (points1[i][1] - points1[j][1])) {
                if (m1[make_pair(points1[i][0], points1[j][1])] > 0
                    && m1[make_pair(points1[j][0], points1[i][1])] > 0) {

                    // より大きな正方形であれば結果を保存
                    if (side1 < abs(points1[i][0] - points1[j][0])
                        || (side1 == abs(points1[i][0] - points1[j][0])
                            && ((points1[i][0] * points1[i][0]
                                 + points1[i][1] * points1[i][1])
                                < (x1 * x1 + y1 * y1)))) {
                        x1 = points1[i][0];
                        y1 = points1[i][1];
                        side1 = abs(points1[i][0] - points1[j][0]);
                    }
                }
            }
            // 削除した点を元に戻す
            m1[make_pair(points1[j][0], points1[j][1])]++;
        }
        // 削除した点を元に戻す
        m1[make_pair(points1[i][0], points1[i][1])]++;
    }

    // 最大の正方形を表示
    if (side1 != -1)
        cout << "Side of the square is : " << side1
             << ", \npoints of the square are " << x1 << ", " << y1
             << " " << (x1 + side1) << ", " << y1
             << " "
             << (x1) << ", " << (y1 + side1)
             << " "
             << (x1 + side1) << ", " << (y1 + side1) << endl;
    else
        cout << "No such square" << endl;
}

// ドライバーコード
int main() {
    const int n1 = 6;
    // 与えられた点
    long long int points1[n1][2] = { { 2, 2 }, { 5, 5 }, { 4, 5 }, { 5, 4 }, { 2, 5 }, { 5, 2 } };

    // 最大の正方形を求める
    findLargestSquare1(points1, n1);
    return 0;
}

実行結果

Side of the square is : 3,
points of the square are 2, 2 5, 2 2, 5 5, 5

コードのポイント

• 対角の2点について x 座標の差と y 座標の差が等しいことを確認することで、軸に平行な正方形の候補だけを効率よく絞り込んでいます。
• 残りの2点の存在確認は、マップへの参照のみで完結するため、全探索に比べて大幅な高速化が可能です。
• 使用中の点は一時的にマップから減算し、各ループの終了時に加算して復元することで、同じ点の重複利用を防ぎつつ状態を正しく管理しています。
• 一辺の長さが同じ候補が複数ある場合は、原点からの距離（x² + y²）が小さい方を優先して選択します。