C++で平面内に形成できる平行四辺形の数を数えるアルゴリズム

本記事の課題は、平面上に与えられた点集合から形成できる平行四辺形の個数を求めることです。平行四辺形とは、四角形の対辺が互いに平行であり、それに伴って対角も等しくなる四角形のことを指します。

入力 −

int a[] = {0, 2, 5, 5, 2, 5, 2, 5, 2}
int b[] = {0, 0, 1, 4, 3, 8, 7, 11, 10}

出力 − 平面内の平行四辺形の数 − 3

説明 − (x, y) 座標の点が与えられており、これらの点を組み合わせると、図のように 3 つの平行四辺形を形成できます。

入力 −

a[] = {0, 3, 1, 4, 1, 5}
b[] = {0, 1, 3, 4, 4, 4}

出力 − 平面内の平行四辺形の数 − 1

説明 − (x, y) 座標の点が与えられており、これらの点を組み合わせると、図のように 1 つの平行四辺形を形成できます。

アプローチの鍵となる性質

この問題を効率的に解く鍵は、「平行四辺形の対角線は互いの中点で交わる」という幾何学的性質です。つまり、2 つの線分がまったく同じ中点を持つとき、その 4 つの端点は必ず平行四辺形を形成します。

そこで、すべての点ペアについて対角線の候補となる中点を計算し、map を使って同じ中点が何回出現したかを記録します。ある中点が n 回出現した場合、その中点を共有する点ペアの組み合わせ nC2 = n × (n − 1) / 2 個が、そのまま平行四辺形の個数になります。

プログラムで使用するアプローチ

• x 座標の値を格納する array_1 と、y 座標の値を格納する array_2 を入力として受け取る

• array_1 のサイズを計算し、そのデータを処理用の関数に渡す

• 座標ペアをキーとして整数型データを格納するための map 型変数を作成する

• 形成できる平行四辺形の総数を格納する一時変数 count を用意する

• i を 0 から array_1 のサイズまで回す FOR ループを開始する

• 内側に、j を i+1 から array_1 のサイズまで回す FOR ループを開始する

• ループ内で、a_mid に a[i] + a[j] を、b_mid に b[i] + b[j] を設定する（2 点の座標の和＝中点の 2 倍に相当）

• map のキー (a_mid, b_mid) に対応する出現回数を 1 ずつインクリメントする

• map を先頭から末尾まで走査する別のループを開始する

• ループ内で、各ペアの出現回数を一時変数 temp に取得する

• count に temp * (temp − 1) / 2 を加算する

• count を返し、結果を出力する

実装例

#include <bits/stdc++.h>
using namespace std;
//平面内の平行四辺形の数を数える
int parallelogram(int a[], int b[], int size){
    map<pair<int, int>, int> um;
    int count = 0;
    for (int i=0; i<size; i++){
        for (int j=i+1; j<size; j++){
            int a_mid = a[i] + a[j];
            int b_mid = b[i] + b[j];
            um[make_pair(a_mid, b_mid)]++;
        }
    }
    for (auto it = um.begin(); it != um.end(); it++){
        int temp = it->second;
        count+= temp*(temp - 1)/2;
    }
    return count;
}
int main(){
    int a[] = {0, 3, 1, 4, 1, 5};
    int b[] = {0, 1, 3, 4, 4, 4};
    int size = sizeof(a) / sizeof(int);
    cout<<"平面内の平行四辺形の数: "<<parallelogram(a, b, size) << endl;
    return 0;
}

出力

上記のコードを実行すると、次の出力が得られます −

平面内の平行四辺形の数: 1

このアルゴリズムの計算量は、点の数を N とすると、すべての点ペアを走査するのに O(N²)、map の操作に O(log N) かかるため、全体で O(N² log N) となります。4 つの点を総当たりで調べる O(N⁴) の素朴な手法と比べ、大幅に効率化できる点がこのアプローチの大きな利点です。