2D 평면의 점 수를 나타내는 두 개의 변수 n과 m이 제공됩니다. n개의 점 중에서 m개의 점은 동일선상에 있습니다. 목표는 이 n개의 점을 사용하여 만들 수 있는 삼각형의 수를 찾는 것입니다.
공선점 − 같은 선에 있는 점을 동일선상이라고 합니다. 점 A와 B는 동일선상에 있습니다.
주어진 n=4 (A,B,C,D ) , m=2 (A,B)
삼각형의 수 -
4점 중 3점 선택 =4C3
그러나 동일선상에 있는 점은 삼각형을 형성할 수 없으므로 위에서 계산될 가능한 삼각형을 제거하십시오 =2C3
총 삼각형 =4C3 - 2C3 =4-0 =4 ( ABC, ACD, BCD, ABD )
n 및 m =nC3의 경우 - mC3
예를 들어 이해합시다.
입력 - n=5, m=3
출력 − m개의 동일선상에 있는 총 n개의 점이 있는 삼각형의 개수는 − 9
설명 − 총 삼각형 =5C3 - 3C3 =10 - 1 =9
입력 - n=10, m=5
출력 − m개의 동일선상에 있는 총 n개의 점이 있는 삼각형의 개수는 − 110입니다.
설명 − 총 삼각형 =10C3 - 5C3 =120 - 10 =110
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
조합 계산을 포함하는 파스칼 삼각형을 만들 것입니다. 모든 행은 이전 행 열을 더하여 계산됩니다.
-
여러 점에 대한 입력으로 변수 n과 m을 사용합니다.
-
collinear_points(int n,int m) 함수는 n과 m을 취하여 m이 동일선상에 있는 총 n개의 점이 있는 삼각형의 개수를 반환합니다.
-
세트 카운트 =check(n, 3) - check(m, 3); ( nC3 계산용 - mC3 )
-
함수 검사(int n, int r)는 n과 r을 취하고 nCr 값을 반환합니다.
-
길이가 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]로 계산합니다.
-
결국 우리는 nCr로 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