Trong bài toán này, chúng ta được cho n điểm nằm trên mặt phẳng 2D, mỗi điểm có tọa độ (x, y). Nhiệm vụ là giải quyết các truy vấn. Đối với mỗi truy vấn, ta được cho một số nguyên R. Cần tìm số lượng điểm nằm bên trong đường tròn tâm tại gốc tọa độ (0, 0) và bán kính R.
Mô tả bài toán
Với mỗi truy vấn, ta cần tìm tổng số điểm trong n điểm cho trước mà nằm bên trong đường tròn (tức là trong hoặc trên đường tròn) có bán kính R và tâm tại gốc tọa độ (0, 0).
Ví dụ minh họa
Đầ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 – Với truy vấn bán kính 2, điểm (-1, 0) nằm bên trong đường tròn, còn tất cả các điểm khác nằm bên ngoài.
Phương trình toán học của đường tròn tâm (0,0) là: x² + y² = r². Do đó, một điểm (x, y) nằm bên trong hoặc trên đường tròn khi thỏa mãn: x² + y² ≤ r².
Để giải bài toán, cách tiếp cận đơn giản là duyệt qua tất cả các điểm cho mỗi truy vấn và kiểm tra xem điểm đó có thỏa mãn điều kiện x² + y² ≤ R² hay không.
Chương trình minh họa cách giải cơ bản:
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
Độ phức tạp thời gian của cách giải này là O(n×Q), vì với mỗi truy vấn ta phải tính x² + y² cho tất cả n điểm.
Một cách giải hiệu quả hơn là tiền tính giá trị x² + y² cho tất cả n điểm và lưu vào một mảng, sau đó sắp xếp mảng này. Khi xử lý truy vấn, ta chỉ cần dùng tìm kiếm nhị phân để tìm vị trí đầu tiên mà giá trị lớn hơn R², từ đó biết số điểm thỏa mãn.
Chương trình minh họa cách giải tối ưu:
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];
// Tiền tính giá trị x^2 + y^2
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