数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装学
法学C++中计算圆内点数的查询
在这个问题中，我们给定n个位于二维平面的点，每个点的坐标为(x,y)。我们的任务是解决两个查询。对于每个查询，我们给定一个整数R。我们需要找到位于圆内的点数，该圆的圆心位于原点，半径为R。
问题描述
对于每个查询，我们需要找到n个点中位于半径为R、圆心为原点(0, 0)的圆内（即圆周以内）的点的总数。
让我们举个例子来更好地理解这个问题
输入
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
更新于：2020年9月9日
553 次浏览
广告