DHBB 2017 - NTT - 11 - Bắt ruồi
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Ở xứ ManU ngày nay có một người nổi tiếng tên là Anthony Martial. Anh được mệnh danh là Tia chớp đen nhờ có khả năng bắt ruồi rất nhanh và chính xác. Martial thường quan sát vị trí các chú ruồi rồi tung một cú đập trúng một lúc vài ba con liền.
Trên mặt bàn được xem là mặt phẳng Oxy, có ~N~ con ruồi, con thứ ~i~ ở vị trí tọa độ ~(x_i, y_i)~ và không có 2 con ruồi nào ở cùng một chỗ.
Martial dùng một chiếc vỉ đập ruồi hình tròn có bán kính ~R~ và đập liên tiếp ~M~ lần xuống bàn. Ruồi bị bắt nếu vỉ đập ruồi phủ lên vị trí nó đang ở.
Yêu cầu: Tính số ruồi mà Martial bắt được sau ~M~ lần đập. Biết rằng khoảng thời gian giữa các lần đập ruồi là không đáng kể, các chú ruồi không kịp bay đi sau mỗi lần đập.
Input
- Dòng đầu tiên chứa số nguyên dương ~N, M, R~.
- Dòng thứ ~i~ trong ~N~ dòng tiếp theo chứa 2 số nguyên ~x_i, y_i~ là tọa độ nơi những con ruồi đang đậu.
- Dòng thứ ~j~ trong ~M~ dòng tiếp theo chứa 2 số nguyên ~z_j, t_j~ là tọa độ tâm của vỉ đập ruồi lần thứ ~j~.
- Với ~-10^5 \le x_i, y_i, z_j, t_j \le 10^5~; ~R \le 10^9~.
Output
- Ghi ra số nguyên duy nhất là số ruồi mà Martial bắt được sau ~M~ lần đập.
Bình luận