C++를 사용하여 세 줄의 점 집합에서 형성되는 삼각형의 수 찾기

우리는 지금 3줄에 있는 몇 가지 포인트가 주어집니다. 예를 들어 이 점이 형성할 수 있는 삼각형의 수를 찾아야 합니다.

Input: m = 3, n = 4, k = 5
Output: 205

Input: m = 2, n = 2, k = 1
Output: 10

우리는 이 질문에 몇 가지 조합을 적용하고 이 문제를 해결하기 위한 몇 가지 공식을 만들 것입니다.

해결책을 찾기 위한 접근 방식

이 접근 방식에서는 현재 상황에 조합론을 적용하여 공식을 고안하고 이 공식이 결과를 제공합니다.

위 접근 방식에 대한 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); // the combination of n with 3.
   long long linem = comb(m, 3); // the combination of m with 3.
   long long liner = comb(r, 3); //the combination of r with 3.
   long long answer = comb(n + m + r, 3); // all possible comb of n, m , r with 3.
   answer -= (linen + linem + liner);
   cout << answer << "\n";
   return 0;
}

출력

205

위 코드 설명

이 접근법에서 우리는 n+m+r과 3의 가능한 모든 조합을 찾습니다. 즉, comb(n+m+r, 3). 이제 알다시피 3개의 점이 삼각형이 되기 위한 조건은 동일선상에 있어서는 안 된다는 것이므로 n, m, r과 3의 조합의 합인 가능한 모든 동일선상 점을 찾습니다. 이 합계를 n+m+r의 다양성으로 빼서 3으로 답을 구하고 인쇄합니다.

결론

이 기사에서는 몇 가지 조합을 적용하여 세 개의 선에 있는 점 집합에서 몇 개의 삼각형을 만들 수 있는지에 대해 설명했습니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결하는 완전한 접근 방식(Normal)을 배웠습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 기사가 도움이 되기를 바랍니다.