【C++】2次元空間上の点のトリプル(A, B, C)のうち、中点条件を満たす組み合わせを数える方法

問題の概要

2次元平面上に与えられたN個の点の中から、「ある1点が他の2点を結ぶ線分の中点になっている」ような3点の組み合わせ(トリプル)の総数を求めるのがこの問題の目標です。トリプルを(A, B, C)としたとき、BがAとCの中点になっていれば条件を満たします(どの点が中点になっても構いません)。

解き方の基本アイデアは次のとおりです。まず、すべての点を pair<int,int> 型として vector に格納し、さらにその全要素を set にも追加します。次に set 内から2点を選び、その(x, y)座標の合計を2で割った値が同じ set 内に存在するかどうかを調べます。存在すれば、その2点の中点にあたる点が集合内にあることになるため、トリプルのカウントを1つ増やします。

具体例で確認してみましょう。

入力

{ 1,2 }, { 4,2 }, { 2,1 }, { 7,2 } ※N=4

出力

条件を満たすトリプルペアの数: 1

説明

{4,2} は {1,2} と {7,2} の中点です。該当するトリプルはこの1つだけです。

入力

{ 1,2 }, { 4,2 }, { 2,1 }, { 5,2 }, { 8,1 }, { 1,1 } ※N=6

出力

条件を満たすトリプルペアの数: 0

説明

中点となる点を持つ3点の組み合わせは存在しません。

プログラムで使用しているアプローチ

• pair<int,int> 型のペアを格納する vector を使用します。
• 各ペアには点の(x, y)座標が格納されます。
• 関数 mid_point(vector<pair<int,int>> vec, int size) は、ベクターとそのサイズを引数に取り、中点条件を満たすトリプルの数を返します。
• 該当するトリプルを数えるための変数 count を0で初期化します。
• vector 内のすべてのペアを set<pair<int,int>> に挿入します。これにより、重複のない全点の集合が得られます。
• 二重の for ループを使って、すべての点のペア(i番目とj番目、j>i)について走査します。
• 2点のx座標の合計を整数 point_A に、y座標の合計を整数 point_B に格納します。
• point_A と point_B の両方が偶数である場合のみ、中点条件の判定を行います。和が奇数だと中点が整数座標にならないため、ここで無駄な探索を省けます。
• (point_A/2, point_B/2) というペアが set 内に存在すれば中点が存在することになるので、count を1増やします。
• ループ終了後、count を結果として返します。

コード例

#include <bits/stdc++.h>
using namespace std;
int mid_point(vector<pair<int, int>> vec, int size){
    int count = 0;
    set<pair<int, int> > sets;
    for (int i = 0; i < size; i++){
        sets.insert(vec[i]);
    }
    for (int i = 0; i < size; i++){
        for (int j = i + 1; j < size; j++){
            int point_A = vec[i].first + vec[j].first;
            int point_B = vec[i].second + vec[j].second;
            if (point_A % 2 == 0 && point_B % 2 == 0){
                if (sets.find(make_pair(point_A / 2, point_B / 2)) != sets.end()){
                    count++;
                }
            }
        }
    }
    return count;
}
int main(){
    vector<pair<int, int>> vec = { { 9, 2 }, { 5, 2 }, { 1, 2 } };
    int size = vec.size();
    cout<<"Count of triplet pairs (A, B, C) of points in 2-D space that satisfy the given condition are: "<<mid_point(vec, size);
}

出力

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

Count of triplet pairs (A, B, C) of points in 2-D space that satisfy the given condition are: 1

計算量の目安

すべての点のペアを列挙するのに O(N²)、set 内の探索に O(log N) かかるため、全体の時間計算量は O(N² log N) となります。また、点を格納する set の分だけ O(N) の追加メモリが必要です。ハッシュセット(unordered_set)をカスタムハッシュ付きで使えば、平均 O(N²) まで高速化することも可能です。