Vườn cây

View as PDF

Submit solution

Points: 1.36 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
HSG Duyên hải và Ðồng bằng Bắc Bộ
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Bờm vừa thắng cược Phú Ông và phần thưởng là lấy tất cả các cây gỗ sưa trong vườn của Phú Ông. Thấy Phú Ông thẫn thờ vì mất cây, Bờm liền đưa cho Phú Ông một sợi dây và nói: "Ông hãy chọn một số cây, những cây còn lại tôi sẽ lấy đi, chú ý rằng, sau khi tôi lấy cây đi thì những cây còn lại phải bao được bằng sợi dây này". Phú Ông đồng ý ngay và tìm cách chọn cây sao cho giữ lại được nhiều cây nhất. Giả sử vườn cây của Phú Ông có ~n~ cây và coi mỗi cây như một hình tròn trên mặt phẳng, các cây có cùng bán kính ~r~, cây thứ ~i~ có tọa độ tâm ~(x_i~, ~y_i)~.

Yêu cầu:

Cho ~d~ là độ dài sợi dây và tọa độ tâm của ~n~ cây, các cây có bán kính ~r~. Hãy giúp Phú Ông tìm cách chọn để giữ lại nhiều cây nhất.

Input

Dòng đầu tiên ghi số nguyên dương ~K~ là số lượng bộ dữ liệu. Tiếp đến là ~K~ nhóm dòng, mỗi nhóm tương ứng với một bộ dữ liệu có cấu trúc như sau:

  • Dòng thứ nhất ghi ba số nguyên dương ~d~, ~n~ và ~r~ ~(d \leq 10^{9}~; ~r \leq 100)~;
  • ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~x_i~, ~y_i~ ~(|x_i|, |y_i| \leq 1000)~.

Dữ liệu đảm bảo các hình tròn không giao nhau. Các số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Output

Ghi ra thiết bị ra chuẩn gồm ~K~ dòng, mỗi dòng ghi một số nguyên là số lượng cây mà Phú Ông có thể giữ lại được tương ứng với bộ dữ liệu trong file dữ liệu vào.

Giới hạn

  • Subtask ~1~ ~(6~ tests~)~: Giả thiết là ~n \leq 2~.
  • Subtask ~2~ ~(6~ tests~)~: Giả thiết là ~n \leq 3~.
  • Subtask ~3~ ~(8~ tests~)~: Giả thiết là ~n \leq 4~.
  • Subtask ~4~ ~(8~ tests~)~: Giả thiết là ~n \leq 10~.

Sample Input

1
20 4 1
1 1
5 1
7 1
20 20

Sample Output

3

Comments

Please read the guidelines before commenting.


There are no comments at the moment.