Đếm tổng số điểm trong 2 vòng tròn

Question

Có 2 vòng tròn và các trung tâm của chúng được cố định và sẽ được cung cấp làm đầu vào. Sau đó, sẽ có n điểm, các tọa độ x và y trong đó được cho là đầu vào.

Cuối cùng, sẽ có q truy vấn. Đối với mỗi truy vấn, bán kính của hai vòng tròn (Hãy để chúng là r1 và r2) sẽ được cung cấp. Xuất tổng số điểm trong vòng tròn đầu tiên hoặc vòng tròn thứ hai cho mỗi truy vấn. Một điểm nằm bên trong một vòng tròn nếu khoảng cách từ điểm đến trung tâm nhỏ hơn hoặc bằng bán kính của vòng tròn.

Ràng buộc: n, q < = 10^6 r1, r2 < = 10^7 và cho mỗi tọa độ, | x | và | y | < = 10^6

Tôi đang tìm quá trình tiền xử lý O (nlogn) hoặc O (nlog^2n) và sau đó là thuật toán O (logn) cho mỗi truy vấn. Giải pháp O (n) cho mỗi truy vấn quá chậm. Bất kỳ ý tưởng làm thế nào để crack này?

Answer 1

Cho C1, C2 là trung tâm của đĩa. Cho Pi, i = 1 ... n, là điểm. Gọi Qj, j = 1 ... q, là truy vấn thứ j, Qj = (qj1, qj2).

1. Đối với mỗi điểm Pi, tính d (Pi, Ck), k = 1 hoặc 2. Đặt nó trong một bội số được sắp xếp: Mk (d (Pi, Ck)) chứa Pi. Điều này có thể được thực hiện trong O (nlogn) (điều này thực sự giống như sắp xếp danh sách khoảng cách).
2. Đối với mỗi truy vấn Qj, thực hiện tìm kiếm nhị phân qjk trên các phím của Mk, có thể được thực hiện trong O (logn).
3. Đối với mỗi truy vấn Qj, hãy kết hợp các giá trị của bội số trên các phím nhỏ hơn hoặc bằng giá trị bạn tìm thấy ở trên.

Answer 2

Giải pháp với thời gian truy vấn O (log N).

1. Sẽ dễ dàng hơn cho mỗi truy vấn đếm điểm ngoài vòng tròn, sau đó trừ kết quả khỏi tổng số điểm.
2. Dễ dàng hơn khi sử dụng tọa độ Descartes. Vì vậy mà X sẽ là khoảng cách từ C1, Y - khoảng cách từ C2. Trong trường hợp này, chúng ta chỉ cần tìm số điểm trong khu vực X > r1 && Y > r2.
3. Gán giá trị "1" cho mỗi điểm. Bây giờ chúng ta chỉ cần tìm tổng các giá trị trong khu vực đã cho. Trong trường hợp 1D, điều này có thể được thực hiện với cây Fenwick. Nhưng trường hợp 2D không khác nhiều nếu cây 2D Fenwick được sử dụng.
4. Cây Fenwick 2D nên chiếm quá nhiều không gian (10 giá trị có giới hạn nhất định). Nhưng mảng 2D cho cây Fenwick rất thưa thớt, vì vậy chúng tôi có thể sử dụng bản đồ băm để lưu trữ giá trị của nó và giảm yêu cầu về không gian (và thời gian xử lý trước) thành O (N log N).