इस समस्या में, हमें n बिंदु दिए गए हैं जो एक 2D तल पर स्थित हैं, प्रत्येक निर्देशांक (x,y) है। हमारा काम दो प्रश्नों को हल करना है। प्रत्येक प्रश्न के लिए, हमें एक पूर्णांक R दिया जाता है। हमें वृत्त के केंद्र को मूल बिंदु और त्रिज्या R लेते हुए, वृत्त के अंदर स्थित बिंदुओं की संख्या ज्ञात करने की आवश्यकता है।
समस्या का विवरण
प्रत्येक प्रश्न के लिए, हमें त्रिज्या R और केंद्र बिंदु मूल (0, 0) के वृत्त के अंदर (अर्थात परिधि के अंदर) स्थित n बिंदुओं में से कुल बिंदुओं की संख्या ज्ञात करनी होगी।
समस्या को बेहतर ढंग से समझने के लिए एक उदाहरण लेते हैं
इनपुट
n = 4 2 1 1 2 3 3 -1 0 -2 -2 Query 1: 2
आउटपुट
1
स्पष्टीकरण - हमारे प्रश्न के लिए, त्रिज्या 2 है, बिंदु -1 0, वृत्त के अंदर स्थित है, और अन्य सभी इसके बाहर स्थित हैं।
वृत्त का गणितीय समीकरण (x2 - x1)2 + (x2 - x1)2 =r2 है। तो, एक बिंदु के लिए वृत्त के अंदर स्थित है जिसका केंद्र (0,0) है। बिंदु (x,y) को x2 + y2 <=r2 को संतुष्ट करना चाहिए।
इस समस्या को हल करने के लिए, एक सरल तरीका यह होगा कि प्रत्येक प्रश्न के लिए सभी बिंदुओं को पार किया जाए और यह जांचा जाए कि यह वृत्त की परिधि के अंदर है या नहीं, सूत्र का उपयोग नहीं कर रहा है।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#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<<"For Query "<<(i+1)<<": The number of points that lie inside the circle is "<<solveQuery(x, y, n, query[i])<<"\n";
return 0;
} आउटपुट
For Query 1: The number of points that lie inside the circle is 4 For Query 2: The number of points that lie inside the circle is 1
इस दृष्टिकोण का उपयोग करके समस्या के समाधान में O(n*Q) की समय जटिलता होगी। क्योंकि प्रत्येक क्वेरी के लिए, हम सभी n बिंदुओं के लिए x2 + y2 के मान की गणना करेंगे।
तो, एक कुशल समाधान सभी n बिंदुओं के लिए x2 + y2 के मान को पूर्व-गणना करके किया जाएगा। और इसे एक सरणी में संग्रहीत करना जिसका उपयोग सभी प्रश्नों के लिए किया जा सकता है। और फिर प्रत्येक प्रश्न का समाधान खोजें। प्रोग्राम को और अधिक अनुकूलित करने के लिए, हम सरणी को सॉर्ट कर सकते हैं और फिर सर्कल से बाहर पहला तत्व ढूंढ सकते हैं। लिए गए समय को बेहतर बनाने के लिए।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,
उदाहरण
#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];
// Precomputing Values
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<<"For Query "<<(i+1)<<": The number of points that lie inside the circle is " <<solveQuery(points, n, query[i])<<"\n";
return 0;
}
आउटपुट
For Query 1: The number of points that lie inside the circle is 4 For Query 2: The number of points that lie inside the circle is 1