समस्या विवरण
इस समस्या में, हमें एक 2D तल पर n बिंदु दिए गए हैं, जिनमें से प्रत्येक के निर्देशांक (x, y) हैं। हमारा कार्य क्वेरीज़ को हल करना है। प्रत्येक क्वेरी के लिए, हमें एक पूर्णांक R दिया जाता है। हमें उन बिंदुओं की संख्या ज्ञात करनी है जो मूल बिंदु (0, 0) को केंद्र और त्रिज्या R वाले वृत्त के अंदर स्थित हैं।
उदाहरण
इनपुट
n = 4 बिंदु: (2, 1), (1, 2), (3, 3), (-1, 0), (-2, -2) क्वेरी 1: R = 2
आउटपुट
1
व्याख्या - क्वेरी के लिए त्रिज्या 2 है, बिंदु (-1, 0) वृत्त के अंदर स्थित है, जबकि अन्य सभी बिंदु बाहर हैं।
मूल बिंदु (0,0) को केंद्र वाले वृत्त का गणितीय समीकरण है: x² + y² ≤ r²। इसलिए, एक बिंदु (x, y) वृत्त के अंदर स्थित होगा यदि x² + y² ≤ r² संतुष्ट होता है।
सरल दृष्टिकोण
इस समस्या को हल करने का एक सरल तरीका है प्रत्येक क्वेरी के लिए सभी बिंदुओं को पार करना और सूत्र का उपयोग करके जांचना कि क्या वे वृत्त की परिधि के अंदर स्थित हैं या नहीं।
कार्यक्रम उदाहरण
#include <iostream>
using namespace std;
int solveQuery(int x[], int y[], int n, int R) {
int count = 0;
for(int i = 0; i < n; i++) {
if(((x[i]*x[i]) + (y[i]*y[i])) <= (R*R))
count++;
}
return count;
}
int main() {
int x[] = { 2, 1, 3, -1, -2 };
int y[] = { 1, 2, 3, 0, -2 };
int n = sizeof(x) / sizeof(x[0]);
int Q = 2;
int query[] = {4, 2 };
for(int i = 0; i < Q; i++)
cout << "क्वेरी " << (i+1) << ": वृत्त के अंदर स्थित बिंदुओं की संख्या " << solveQuery(x, y, n, query[i]) << "\n";
return 0;
}
आउटपुट
क्वेरी 1: वृत्त के अंदर स्थित बिंदुओं की संख्या 4 क्वेरी 2: वृत्त के अंदर स्थित बिंदुओं की संख्या 1
इस दृष्टिकोण का उपयोग करके समाधान की समय जटिलता O(n*Q) होगी। क्योंकि प्रत्येक क्वेरी के लिए, हम सभी n बिंदुओं के लिए x² + y² का मान गणना करेंगे।
कुशल समाधान
एक कुशल समाधान यह होगा कि हम सभी n बिंदुओं के लिए x² + y² के मान की पूर्व-गणना (precompute) करें और इसे एक सरणी में संग्रहीत करें जिसका उपयोग सभी क्वेरीज़ के लिए किया जा सके। और फिर प्रत्येक क्वेरी के लिए समाधान खोजें। प्रोग्राम को और अनुकूलित करने के लिए, हम सरणी को क्रमबद्ध (sort) कर सकते हैं और फिर उस पहले तत्व को ढूंढ सकते हैं जो वृत्त के बाहर स्थित है। इससे समय कम लगेगा।
कार्यक्रम उदाहरण
#include <bits/stdc++.h>
using namespace std;
int solveQuery(int points[], int n, int rad) {
int l = 0, r = n - 1;
while ((r - l) > 1) {
int mid = (l + r) / 2;
if (points[mid] > (rad * rad))
r = mid - 1;
else
l = mid;
}
if ((sqrt(points[l])) > (rad * 1.0))
return 0;
else if ((sqrt(points[r])) <= (rad * 1.0))
return r + 1;
else
return l + 1;
}
int main() {
int n = 5;
int point[n][2] = { {2, 1}, {1, 2}, {3, 3}, {-1, 0}, {-2, -2} };
int Q = 2;
int query[] = {4, 2 };
int points[n];
// मानों की पूर्व-गणना
for (int i = 0; i < n; i++)
points[i] = ( point[i][0]*point[i][0] ) + ( point[i][1]*point[i][1] );
sort(points, points + n);
for(int i = 0; i < Q; i++)
cout << "क्वेरी " << (i+1) << ": वृत्त के अंदर स्थित बिंदुओं की संख्या "
<< solveQuery(points, n, query[i]) << "\n";
return 0;
}
आउटपुट
क्वेरी 1: वृत्त के अंदर स्थित बिंदुओं की संख्या 4 क्वेरी 2: वृत्त के अंदर स्थित बिंदुओं की संख्या 1