【C++】n個の点のうちm個が同一直線上にあるときに作れる三角形の数を求める方法

問題の概要

2次元平面上の点の総数を表す2つの変数 n と m が与えられます。このうち m 個の点は同一直線上（コリニア）に並んでいます。ここでの課題は、これら n 個の点から作ることができる三角形の数を求めることです。

同一直線上の点（共線点）とは、同じ一本の直線上に乗っている点のことです。例えば下図では、点 A と点 B が同一の直線上に位置しています。

考え方の基本

まず、n=4（A, B, C, D）、m=2（A, B）という具体例で確認してみましょう。

三角形の数は次の手順で計算できます。

・4 点から任意の 3 点を選ぶ組み合わせ = 4C₃
・ただし、同一直線上の点だけでは三角形が成立しないため、先の計算に含まれる無効な組み合わせを差し引く = 2C₃
・合計 = 4C₃ − 2C₃ = 4 − 0 = 4（ABC、ACD、BCD、ABD）

これを一般化すると、答えは次の公式で表せます。

三角形の数 = nC₃ − mC₃

入力例と出力例

入力：n=5、m=3
出力：9
解説：5C₃ − 3C₃ = 10 − 1 = 9

入力：n=10、m=5
出力：110
解説：10C₃ − 5C₃ = 120 − 10 = 110

プログラムで使うアプローチ

組み合わせの計算を効率的に行うために、パスカルの三角形を利用します。各行は、前の行の隣り合う列同士を足し合わせることで順に求められます。処理の流れは以下の通りです。

• 点の数として変数 n と m を入力します。
• 関数 collinear_points(int n, int m) が n と m を受け取り、m 個が同一直線上にある n 点から作れる三角形の数を返します。
• count = check(n, 3) − check(m, 3) として、nC₃ − mC₃ を計算します。
• 関数 check(int n, int r) は n と r を受け取り、nC_r の値を返します。
• 長さ r+1 の配列 arr を用意します。
• memset を使って配列全体を 0 で初期化します。
• arr[0] = 1 を設定します。
• i=0〜n、j=min(i,r)〜j>0 の二重ループでパスカルの三角形を構築し、arr[j] = arr[j] + arr[j-1] と更新していきます。
• 最終的に arr[r] が nC_r の値となるので、それを返します。
• check() の処理が完了すれば、三角形の数が求められます。
• count を結果として返します。

この手法の計算量は O(n × r) であり、階乗を直接計算する方法と比べてオーバーフローのリスクを抑えつつ安定して組み合わせを求められるのが利点です。

C++実装例

#include <bits/stdc++.h>
using namespace std;
int check(int n, int r){
    int arr[r+1];
    memset(arr, 0, sizeof(arr));
    arr[0] = 1;
    for (int i = 1; i <= n; i++){
        for (int j = min(i, r); j > 0; j--){
            arr[j] = arr[j] + arr[j-1];
        }
    }
    return arr[r];
}
int collinear_points(int n,int m){
    int count = check(n, 3) - check(m, 3);
    return count;
}
int main(){
    int n = 6, m = 2;
    cout<<"n個の点のうちm個が同一直線上にある場合に作れる三角形の数: "<< collinear_points(n, m);
    return 0;
}

出力

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

n個の点のうちm個が同一直線上にある場合に作れる三角形の数: 20

この結果は、6C₃ − 2C₃ = 20 − 0 = 20 となり、公式どおりの値が正しく求まっていることが分かります。