हमें N रेखाएं दी गई हैं, प्रत्येक दो बिंदुओं (x1,y1) और (x2,y2) द्वारा परिभाषित। लक्ष्य: दी गई रेखाओं में से अधिकतम संख्या ढूंढें जो एक ही बिंदु से गुजर सकती हैं, ऐसी शर्त के साथ कि कोई दो रेखाएं एक-दूसरे को ओवरलैप न करें, और कोई रोटेशन न किया जाए।
दृष्टिकोण
- रेखाओं को जोड़ी (m, c) के रूप में दर्शाएं जहां y = mx + c
- ढलान m = (y2 - y1) / (x2 - x1)
- समान m वाली रेखाएं समानांतर होती हैं (यदि c1 ≠ c2)
- अद्वितीय ढलानों (m) की गिनती करें - प्रत्येक अद्वितीय ढलान एक रेखा का प्रतिनिधित्व करती है जो एक सामान्य बिंदु से गुजर सकती है
- लंबवत रेखाओं के लिए (x1 = x2), ढलान = INT_MAX (या एक बड़ा मान) मानें
उदाहरण 1
रेखा 1: (4,10) से (2,2) → m = (2-10)/(2-4) = -8/-2 = 4 रेखा 2: (2,2) से (1,1) → m = (1-2)/(1-2) = -1/-1 = 1 अद्वितीय ढलानें: 4, 1 → अधिकतम रेखाएं: 2
उदाहरण 2
रेखा 1: (1,5) से (3,2) → m = (2-5)/(3-1) = -3/2 = -1.5 रेखा 2: (2,7) से (2,8) → x1=x2, लंबवत → m = INT_MAX अद्वितीय ढलानें: -1.5, INT_MAX → अधिकतम रेखाएं: 2
C प्रोग्राम
#include <stdio.h>
#include <limits.h>
int numLines(int n, int x1[], int y1[], int x2[], int y2[]) {
double slopes[100];
int k = 0;
double slope;
for(int i = 0; i < n; i++) {
if(x1[i] == x2[i]) {
slope = INT_MAX; // लंबवत रेखा
} else {
slope = (double)(y2[i] - y1[i]) / (x2[i] - x1[i]);
}
// जांचें कि क्या यह ढलान पहले से मौजूद है
int found = 0;
for(int j = 0; j < k; j++) {
if(slopes[j] == slope) {
found = 1;
break;
}
}
if(!found) {
slopes[k++] = slope;
}
}
return k;
}
int main() {
int n = 2;
int x1[] = {1, 5}, y1[] = {3, 2};
int x2[] = {2, 7}, y2[] = {2, 8};
printf("अधिकतम विशिष्ट रेखाएं: %d\n", numLines(n, x1, y1, x2, y2));
return 0;
}
आउटपुट
अधिकतम विशिष्ट रेखाएं: 2
सुधार: फ्लोटिंग-पॉइंट तुलना
ढलानों की तुलना करते समय फ्लोटिंग-पॉइंट सटीकता समस्याओं से बचने के लिए:
// भिन्न के रूप में संग्रहीत करें: (dy, dx) को GCD से सरल करके
typedef struct { int dy, dx; } Slope;
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
Slope normalize(int dy, int dx) {
if(dx < 0) { dy = -dy; dx = -dx; }
int g = gcd(abs(dy), abs(dx));
return (Slope){dy/g, dx/g};
}
// लंबवत रेखा के लिए: {1, 0} या {-1, 0}
जटिलता
- समय: O(n²) सरल सरणी खोज के साथ, O(n log n) सॉर्टिंग/हैशिंग के साथ
- स्थान: O(n)
