点数查询位于C ++中的圆内

在这个问题中，我们得到了位于2D平面上的n个点，每个坐标是(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];
   //预计算值
   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