हमें दो चर n और m दिए गए हैं जो 2D तल पर बिंदुओं की संख्या दर्शाते हैं। n बिंदुओं में से, m बिंदु संरेखीय (collinear) हैं। लक्ष्य इन n बिंदुओं का उपयोग करके बनने वाले त्रिभुजों की संख्या ढूंढना है।
संरेखीय बिंदु (Collinear points) - वे बिंदु जो एक ही रेखा पर होते हैं उन्हें संरेखीय कहा जाता है। बिंदु A और B संरेखीय हैं।
दिया गया n=4 (A,B,C,D), m=2 (A,B)
त्रिभुजों की संख्या -
4 में से किन्हीं तीन बिंदुओं को चुनना = 4C₃
लेकिन संरेखीय बिंदु त्रिभुज नहीं बना सकते इसलिए ऊपर गिने गए संभावित त्रिभुजों को हटा दें = 2C₃
कुल त्रिभुज = 4C₃ - 2C₃ = 4-0 = 4 (ABC, ACD, BCD, ABD)
n और m के लिए = nC₃ - mC₃
आइए उदाहरणों से समझते हैं।
इनपुट - n=5, m=3
आउटपुट - कुल n बिंदुओं और m संरेखीय बिंदुओं वाले त्रिभुजों की गिनती - 9
व्याख्या - कुल त्रिभुज = 5C₃ - 3C₃ = 10 - 1 = 9
इनपुट - n=10, m=5
आउटपुट - कुल n बिंदुओं और m संरेखीय बिंदुओं वाले त्रिभुजों की गिनती - 110
व्याख्या - कुल त्रिभुज = 10C₃ - 5C₃ = 120 - 10 = 110
नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण
हम संयोजनों की गणना के लिए पास्कल त्रिभुज बनाएंगे। प्रत्येक पंक्ति की गणना पिछली पंक्ति के कॉलम के जोड़ का उपयोग करके की जाती है।
- बिंदुओं की संख्या के लिए चर n और m को इनपुट के रूप में लें।
- फ़ंक्शन collinear_points(int n,int m) n और m लेता है और कुल n बिंदुओं और m संरेखीय बिंदुओं वाले त्रिभुजों की गिनती वापस करता है।
- count = check(n, 3) - check(m, 3) सेट करें; (nC₃ - mC₃ की गणना के लिए)
- फ़ंक्शन check(int n, int r) n और r लेता है और nCᵣ का मान वापस करता है
- लंबाई r+1 की एक सरणी arr लें।
- memset का उपयोग करके पूरी सरणी को 0 से सेट करें।
- arr[0] = 1 सेट करें।
- i=0 से i<=n तक दो फॉर लूप का उपयोग करके। और j=min(i,r) से j>0 तक पास्कल त्रिभुज की गणना करें arr[j]=arr[j]+arr[j-1] के रूप में।
- अंत में हमें arr[r] nCᵣ के रूप में मिलेगा। इसे वापस करें।
- फ़ंक्शन 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
