資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告