C++で座標の集合から作れる長方形の最小面積を求める方法

問題の概要

XY平面上にいくつかの点が与えられたとします。これらの点から作ることができる長方形のうち、面積が最小になるものを求めます。ただし、長方形の各辺はX軸およびY軸と平行でなければならず、長方形が構成できない場合は0を返します。

例えば、点の集合が [(1, 1), (1, 3), (3, 1), (3, 3), (2, 2)] の場合、(1, 1)、(1, 3)、(3, 1)、(3, 3) の4点を使って長方形を作れるため、答えは4となります。

解法の考え方

この問題を効率よく解くには、まず点をx座標ごとに整理し、同じ縦の直線上にある点同士をグループ化します。続いて、各グループ内の点のペア（例：(x, y1) と (x, y2)）に注目し、このペアを長方形の右側の辺として利用できる最小の長方形を探します。

そのために、それまでに処理した「y座標のペア」と、そのペアが最後に現れたx座標を記録しておきます。同じペア (y1, y2) が過去の別のx座標でも見つかっていれば、2つのx座標を左右の辺、y1とy2を上下の辺とする長方形が確定します。このときの面積は (現在のx − 前回のx) × (y2 − y1) で計算でき、すべての候補を調べながら最小値を更新していきます。最終的に、得られた長方形の面積の最小値を返します。

アルゴリズムの手順

1. すべての点をx座標ごとに分類し、各x座標に紐づくy座標のリストを作成する
2. x座標を昇順にソートしながら各列を走査する
3. 各列の中で、y座標のすべてのペア (y1, y2) を列挙する
4. 同じペアが以前のx座標で記録されていれば、面積 (x − 前回のx) × (y2 − y1) を計算し、最小値を更新する
5. 現在のペアに対して最新のx座標を記録し、処理を続ける

C++による実装例

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <climits>
using namespace std;

int findMinArea(vector<vector<int>>& points) {
    // x座標ごとにy座標をグループ化
    map<int, vector<int>> columns;
    for (const auto& p : points) {
        columns[p[0]].push_back(p[1]);
    }

    // ペア (y1, y2) が最後に現れたx座標を記録
    map<pair<int, int>, int> lastx;
    long long ans = LLONG_MAX;

    for (const auto& [x, col] : columns) {
        vector<int> sortedCol = col;
        sort(sortedCol.begin(), sortedCol.end());
        for (size_t j = 0; j < sortedCol.size(); ++j) {
            for (size_t i = 0; i < j; ++i) {
                pair<int, int> key = {sortedCol[i], sortedCol[j]};
                auto it = lastx.find(key);
                if (it != lastx.end()) {
                    long long area =
                        (long long)(x - it->second) * (key.second - key.first);
                    ans = min(ans, area);
                }
                lastx[key] = x;
            }
        }
    }
    return (ans == LLONG_MAX) ? 0 : static_cast<int>(ans);
}

int main() {
    vector<vector<int>> points = {{1, 1}, {1, 3}, {3, 1}, {3, 3}, {2, 2}};
    cout << "Minimum area of rectangle: " << findMinArea(points) << endl;
    return 0;
}

実行結果

Minimum area of rectangle: 4

計算量の目安

点の総数をNとすると、x座標ごとのグループ化とソートにはO(N log N)、各列内でのy座標ペアの列挙には最悪の場合O(N²)の時間がかかります。必要なメモリはO(N)程度です。点の配置によっては実際の計算量は大きく抑えられるため、実用的な速度で動作します。