C++-এ বৃত্তের ভিতরে পয়েন্ট গণনার কোয়েরি

এই সমস্যাতে, আমাদের একটি ২D সমতলে n সংখ্যক পয়েন্ট দেওয়া আছে, প্রতিটিwhose координаt (x, y)। আমাদের কাজ হলো কোয়েরিগুলো সমাধান করা। প্রতিটি কোয়েরিতে একটি পূর্ণসংখ্যা R দেওয়া থাকে। আমাদেরকে বোয়টি বের করতে হবে যে, মূলবিন্দু (0,0) কে কেন্দ্র ধরে ব্যাসার্ধ R বিশিষ্ট বৃত্তের ভিতরে কতগুলো পয়েন্ট অবস্থিত।

সমস্যা বর্ণনা

প্রতিটি কোয়েরির জন্য, n সংখ্যক পয়েন্টের মধ্যে কতগুলো পয়েন্ট ব্যাসার্ধ R এবং কেন্দ্রবিন্দু মূলবিন্দু (0, 0) বিশিষ্ট বৃত্তের ভিতরে (অর্থাৎ পরিধির অভ্যন্তরে) আছে তা বের করতে হবে।

উদাহরণ দিয়ে বুঝি

ইনপুট

n = 4 
পয়েন্টগুলো: (2, 1), (1, 2), (3, 3), (-1, 0), (-2, -2)
কোয়েরি ১: 2

আউটপুট

1

ব্যাখ্যা − আমাদের কোয়েরিতে ব্যাসার্ধ ২, পয়েন্ট (-1, 0) বৃত্তের ভিতরে অবস্থিত, বাকি সব পয়েন্ট বাহিরে।

বৃত্তের গাণিতিক সমীকরণ হচ্ছে, (x₂ - x₁)² + (y₂ - y₁)² = r²। যেহেতু বৃত্তের কেন্দ্র (0,0), তাই একটি পয়েন্ট (x,y) বৃত্তের ভিতরে থাকার শর্ত হলো x² + y² ≤ r²।

এই সমস্যা সমাধানের একটি সহজ পদ্ধতি হচ্ছে প্রতিটি কোয়েরির জন্য সব পয়েন্ট percorrer করে উপরের ফর্মুলা দিয়ে চেক করা।

সমাধানের কোড উদাহরণ:

উদাহরণ

#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 পয়েন্টের x² + y² হিসাব করতে হয়।

একটি দক্ষ সমাধান হচ্ছে সব পয়েন্টের x² + y² মানগুলো আগে থেকে ক্যালকুলেট করে একটি অ্যারেতে রাখা। তারপর অ্যারেটি সর্ট করে বাইনারি সার্চ দিয়ে দ্রুত ফলাফল বের করা।

অপ্টিমাইজড কোড উদাহরণ:

উদাহরণ

#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<<"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