点数查询位于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，点-10位于圆内，所有其他圆均位于圆外。
圆的数学方程为(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