이 문제에서는 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];
// 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