C++でmが同一線上にある合計nポイントの三角形の数

2D平面上の点の数を表す2つの変数nとmが与えられます。 n個のポイントのうち、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）

nおよびm=nC ₃の場合 -mC ₃

例を挙げて理解しましょう。

入力 − n =5、m =3

出力 −共線がm個の合計n点の三角形の数は− 9

説明 −三角形の合計=5C ₃ -3C ₃ =10-1 =9

入力 − n =10、m =5

出力 −共線がm個の合計n点の三角形の数は− 110

説明 −三角形の合計=10C ₃ -5C ₃ =120-10 =110

以下のプログラムで使用されているアプローチは次のとおりです

組み合わせの計算を含むパスカルの三角形を作成します。すべての行は、前の行の列の加算を使用して計算されます。

• 変数nとmをいくつかの点の入力として使用します。

• 関数collinear_points（int n、int m）は、nとmを取り、m個の共線を持つ合計n個の点を持つ三角形の数を返します。

• セットカウント=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からi<=nまでの2つのforループを使用します。そして、j =min（i、r）to j> 0は、パスカルの三角形をarr [j] =arr [j] +arr[j-1]として計算します。

• 最終的には、arr[r]をnC _rとして取得します。 。返却してください。

• 関数check（）の終了後。三角形の数を取得します

• 結果としてカウントを返します。

例

#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<<"Count of triangles with total n points with m collinear are: "<< collinear_points(n, m);
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Count of triangles with total n points with m collinear are: 20