C++で3本の直線上の点集合から形成できる三角形の個数を求める方法

問題概要

3本の直線上にそれぞれ複数の点が配置されており、これらの点の中から3点を選んで三角形を作るとき、全部でいくつの三角形が作れるかを求めるのが本記事のテーマです。まずは具体例を見てみましょう。

入力:m = 3, n = 4, k = 5
出力:205

入力:m = 2, n = 2, k = 1
出力:10

この問題は、組み合わせ(コンビネーション)の概念を活用することで、専用の数式を導出し、効率的に解くことが可能です。

解法へのアプローチ

本アプローチでは、組み合わせ論を適用して数式を導きます。この数式を用いることで、答えを直接計算できます。

考え方のポイント

3点が三角形を成すための条件は「その3点が同一直線上に存在しないこと」です。したがって、すべての点から3点を選ぶ組み合わせの総数から、各直線上の点から3点を選ぶ同一直線上の組み合わせを差し引けば、三角形の個数が求まります。

上記アプローチのC++コード

以下は、この問題を解くために使用できるC++のコード例です。

サンプルコード

#include <bits/stdc++.h>

#define MOD 1000000007

using namespace std;

long long fact(long long n) {
    if(n <= 1)
    return 1;
    return ((n % MOD) * (fact(n-1) % MOD)) % MOD;
}
long long comb(int n, int r) {
    return (((fact(n)) % MOD) / ((fact(r) % MOD) * (fact(n-r) % MOD)) % MOD);
}

int main() {
    int n = 3;
    int m = 4;
    int r = 5;
    long long linen = comb(n, 3); // n個の点から3点を選ぶ組み合わせ
    long long linem = comb(m, 3); // m個の点から3点を選ぶ組み合わせ
    long long liner = comb(r, 3); // r個の点から3点を選ぶ組み合わせ
    long long answer = comb(n + m + r, 3); // 全点から3点を選ぶ組み合わせ
    answer -= (linen + linem + liner);
    cout << answer << "\n";
    return 0;
}

実行結果

205

コードの解説

このアプローチでは、まずすべての点(n+m+r個)から3点を選ぶ組み合わせ、すなわち comb(n+m+r, 3) を求めます。3点が三角形をなすには同一直線上にあってはならないため、各直線ごとに同一直線上となる組み合わせ、つまり comb(n, 3)、comb(m, 3)、comb(r, 3) の総和を計算します。そして、全体の組み合わせ数からこの総和を差し引けば、答えが得られるので、それを出力します。

まとめ

本記事では、組み合わせ論を応用して、3本の直線上の点集合から形成できる三角形の個数を求める方法について解説しました。さらに、この問題を解くためのC++プログラムと、その完全なアプローチ(通常解法)も併せて学びました。なお、同じロジックはC、Java、Pythonなど他の言語でも同様に実装できます。本記事が読者の方々の学習の一助となれば幸いです。