हमें प्रत्येक पंक्ति के लिए संख्या N और दो बिंदुओं (x1,y1) और (x2,y2) के निर्देशांक दिए गए हैं। लक्ष्य दी गई रेखाओं से उन रेखाओं की अधिकतम संख्या ज्ञात करना है जो एक बिंदु से होकर गुजर सकती हैं जैसे कि कोई भी दो रेखाएँ एक दूसरे को कवर नहीं करती हैं, और कोई रोटेशन नहीं किया जाता है।
हम (m,c) की जोड़ी के रूप में रेखाओं का प्रतिनिधित्व करेंगे जहां y=mx+c और m ढलान है m=y2-y1/x2-x1
समान m वाली रेखाएँ समानांतर दी गई हैं c1!=c2। हम अलग-अलग ढलानों (एम) की गणना करेंगे। लंबवत रेखाओं के लिए यदि x1=x2, ढलान =INT_MAX अन्यथा मी.
आइए हम एक उदाहरण से समझते हैं।
इनपुट
Line 1 (x1,y1)=(4,10) (x2,y2)=(2,2) Line 2 (x1,y1)=(2,2) (x2,y2)=(1,1)
आउटपुट
Maximum lines: 2
स्पष्टीकरण − कुल रेखाएं 2 हैं। दोनों के ढलान अलग-अलग हैं।
इनपुट
Line 1 (x1,y1)=(1,5) (x2,y2)=(3,2) Line 2 (x1,y1)=(2,7) (x2,y2)=(2,8)
आउटपुट
Maximum lines: 2
स्पष्टीकरण − कुल रेखाएं 2 हैं। दोनों के ढलान अलग-अलग हैं।
नीचे दिए गए प्रोग्राम में इस्तेमाल किया गया तरीका इस प्रकार है
-
पूर्णांक सरणी x1[] और x2[] का उपयोग बिंदुओं के निर्देशांक को रेखाओं पर संग्रहीत करने के लिए किया जाता है।
-
फ़ंक्शन numLines(int x1[],int y1[], int x2[], int y2[]) एक बिंदु से गुजरने वाली रेखाओं की संख्या की गणना कर रहा है।
-
ढलान की गणना करने के लिए x1[],y1[],x2[],y2[] में प्रत्येक बिंदु के लिए सूत्र लागू करना और k का उपयोग करके ढलानों की संख्या में वृद्धि करना।
-
Array s[] ढलानों के मान को संग्रहीत करता है।
-
परिणाम में पंक्तियों की संख्या के रूप में k लौटाएं।
उदाहरण
#include <stdio.h>
int numLines(int n, int x1[], int y1[], int x2[], int y2[]){
double s[10];
int k=0;
double slope;
for (int i = 0; i < n; ++i) {
if (x1[i] == x2[i])
slope = 999;
else
slope = (y2[i] - y1[i]) * 1.0 / (x2[i] - x1[i]) * 1.0;
s[k++]=slope;
}
return k;
}
int main(){
int n = 2;
int x1[] = { 1, 5 }, y1[] = { 3, 2 };
int x2[] = { 2,7 }, y2[] = { 2, 8 };
printf("Maximum lines: %d", numLines(n, x1, y1, x2, y2));
return 0;
} आउटपुट
यदि हम उपरोक्त कोड चलाते हैं तो यह निम्न आउटपुट उत्पन्न करेगा -
Maximum distinct lines passing through a single point : 2