ポイント数に関するクエリは、C++の円の内側にあります

この問題では、2D平面上にあるn個の点が与えられ、各座標は（x、y）です。私たちのタスクは2つの解決クエリです。クエリごとに、整数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