C++에서 m개의 동일선상에 있는 총 n개의 점이 있는 삼각형의 수

2D 평면의 점 수를 나타내는 두 개의 변수 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₃ )

• 함수 검사(int n, int r)는 n과 r을 취하고 nC_r 값을 반환합니다.

• 길이가 r+1인 배열 arr를 가져옵니다.

• memset을 사용하여 전체 배열을 0으로 설정합니다.

• arr[0] =1로 설정합니다.

• i=0에서 i<=n까지 두 개의 for 루프를 사용합니다. 그리고 j=min(i,r) ~ j>0은 파스칼 삼각형을 arr[j]=arr[j]+arr[j-1]로 계산합니다.

• 결국 우리는 nC_r로 arr[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