পয়েন্ট গণনার প্রশ্নগুলি C++ এ একটি বৃত্তের মধ্যে থাকে

এই সমস্যায়, আমাদের 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