C++で水平線分と垂直線分の交点から作れる三角形の数を求める方法

本記事では、与えられた水平線分と垂直線分の交点同士を結ぶことで形成できる三角形の数を求めるC++プログラムについて詳しく解説します。

問題の概要

例として、次のような線分が与えられた場面を考えてみましょう。この図には3つの交点が存在します。三角形を作るには3つの頂点が必要となるため、これらの点から作れる三角形の数は「3つの点を選ぶ組み合わせ」、すなわち ³C₃ = 1 通りとなります。

   |
---|--------|--
   |        |
   |  --|---|
   |        |

一般に、交点の総数を n とすると、作れる三角形の数は n 個の点から3点を選ぶ組み合わせ ⁿC₃、つまり n × (n−1) × (n−2) ÷ 6 で求められます。

アプローチ：スイープラインアルゴリズム

本プログラムではスイープライン(Sweep Line)アルゴリズムを採用しています。すべての線分の情報をイベントとして保持し、ある線分の内部にある点が他の線分の内部の点と一致するかどうかを順に確認することで、与えられた線分群のすべての交点を効率よく検出します。その後、得られた交点の組み合わせから三角形の数を簡単に算出できます。

処理の流れは以下のとおりです。

• 各線分を始点・終点のイベントとして登録する(水平線分と垂直線分で種類を区別)
• イベントをx座標を基準にソートする
• BIT(フェニック木)を使い、現在の走査位置で有効な水平線分のy座標を管理する
• 垂直線分のy座標の範囲に含まれる水平線分の本数を数え、交点の総数を求める
• 交点の数 n に対して n × (n−1) × (n−2) ÷ 6 を計算し、三角形の数を導く

この手法の計算量はイベント数を N とすると O(N log N) であり、すべての線分ペアを総当たりで調べる O(N²) の素朴な方法に比べて大幅に高速です。

C++による実装例

#include<bits/stdc++.h>
#define maxy 1000005
#define maxn 10005
using namespace std;
// 交点を格納する構造体
struct i_point {
    int x, y;
    i_point(int a, int b) {
        x = a, y = b;
    }
};
int bit[maxy];
vector < pair <i_point, int> > events;
// 点をソートするための比較関数
bool com_points(pair<i_point, int> &a, pair<i_point, int> &b) {
    if ( a.first.x != b.first.x )
        return a.first.x < b.first.x;
    else {
        if (a.second == 3 && b.second == 3) {
            return true;
        }
        else if (a.second == 1 && b.second == 3) {
            return true;
        }
        else if (a.second == 3 && b.second == 1) {
            return false;
        }
        else if (a.second == 2 && b.second == 3) {
            return false;
        }
        return true;
    }
}
// BIT(フェニック木)を更新する関数
void update_line(int index, int value) {
    while (index < maxn) {
        bit[index] += value;
        index += index & (-index);
    }
}
// 区間の累積和を取得するクエリ関数
int query(int index) {
    int res = 0;
    while (index > 0) {
        res += bit[index];
        index -= index & (-index);
    }
    return res;
}
// 線分を挿入し、イベントとして登録する
void insertLine(i_point a, i_point b) {
    // 水平線分の場合
    if (a.y == b.y) {
        int begin = min(a.x, b.x);
        int end = max(a.x, b.x);
        events.push_back(make_pair(i_point(begin, a.y), 1));
        events.push_back(make_pair(i_point(end, a.y), 2));
    }
    // 垂直線分の場合
    else {
        int top = max(b.y, a.y);
        int bottom = min(b.y, a.y);
        events.push_back(make_pair(i_point(a.x, top), 3));
        events.push_back(make_pair(i_point(a.x, bottom), 3));
    }
}
// 交点の数を計算する
int calc_i_points() {
    int i_points = 0;
    for (int i = 0 ; i < events.size() ; i++) {
        if (events[i].second == 1) {
            update_line(events[i].first.y, 1);
        }
        else if (events[i].second == 2) {
            update_line(events[i].first.y, -1);
        }
        else {
            int bottom = events[i++].first.y;
            int top = events[i].first.y;
            i_points += query(top) - query(bottom);
        }
    }
    return i_points;
}
// 作成可能な三角形の数を計算する
int calc_triangles() {
    int points = calc_i_points();
    if ( points >= 3 )
        return ( points * (points - 1) * (points - 2) ) / 6;
    else
        return 0;
}
int main() {
    insertLine(i_point(3, 2), i_point(3, 13));
    insertLine(i_point(1, 5), i_point(3, 5));
    insertLine(i_point(8, 2), i_point(8, 8));
    insertLine(i_point(3, 4), i_point(6, 4));
    insertLine(i_point(4, 3), i_point(4, 5));
    sort(events.begin(), events.end(), com_points);
    cout << "Possible number of triangles : " << calc_triangles() << endl;
    return 0;
}

出力

Possible number of triangles : 1

この例では5本の線分から3つの交点が検出され、それらの点を結んで作れる三角形は1つであることが確認できました。交点が3つ未満の場合は三角形が成立しないため、プログラムは正しく 0 を返すようになっています。