Trong bài toán này, chúng ta có n điểm nằm trên mặt phẳng 2D, mỗi tọa độ là (x, y). Nhiệm vụ của chúng ta là giải quyết hai truy vấn. Đối với mỗi truy vấn, chúng tôi được cung cấp một số nguyên R. Chúng tôi cần tìm số điểm nằm bên trong hình tròn, lấy tâm của hình tròn tại điểm gốc và bán kính R.
Mô tả sự cố
Đối với mỗi truy vấn, chúng ta cần tìm tổng số điểm trong số n điểm nằm bên trong hình tròn (tức là bên trong chu vi) bán kính R và gốc điểm ở tâm (0, 0).
Hãy lấy một ví dụ để hiểu rõ vấn đề hơn
Đầu vào
n = 4 2 1 1 2 3 3 -1 0 -2 -2 Query 1: 2
Đầu ra
1
Giải thích - Đối với truy vấn của chúng tôi, bán kính là 2, điểm -1 0, nằm bên trong vòng tròn và tất cả các bán kính khác nằm bên ngoài nó.
Phương trình toán học của đường tròn là, (x2 - x1) 2 + (x2 - x1) 2 =r2. Vì vậy, đối với một điểm nằm bên trong đường tròn có tâm là (0,0). Điểm (x, y) phải thỏa mãn x2 + y2 <=r2.
Để giải quyết vấn đề này, một cách tiếp cận đơn giản sẽ là duyệt qua tất cả các điểm cho mỗi truy vấn và kiểm tra xem nó có nằm bên trong chu vi của hình tròn hay không bằng cách sử dụng công thức.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra
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
Giải pháp cho vấn đề sử dụng cách tiếp cận này sẽ có độ phức tạp về thời gian là O (n * Q). Bởi vì đối với mỗi truy vấn, chúng tôi sẽ tính giá trị của x2 + y2, cho tất cả n điểm.
Vì vậy, một giải pháp hiệu quả sẽ bằng cách tính trước giá trị của x2 + y2, cho tất cả n điểm. Và lưu trữ nó vào một mảng có thể được sử dụng cho tất cả các truy vấn. Và sau đó tìm giải pháp cho từng truy vấn. Để tối ưu hóa chương trình hơn nữa, chúng ta có thể sắp xếp mảng và sau đó tìm phần tử đầu tiên nằm ngoài vòng tròn. Để cải thiện thời gian thực hiện.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
}
Đầu ra
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