Giải bài trực tuyến

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 (xi, yi).

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.

Dữ liệu: Vào từ thiết bị vào chuẩn: 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 ≤ 10^9; r ≤ 100);
• n dòng tiếp theo, dòng thứ i chứa hai số nguyên xi, yi (|xi|, |yi| ≤ 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. Kết quả: 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.

Subtask 1 (15/70 điểm): Giả thiết là n ≤ 2.

Subtask 2 (15/70 điểm): Giả thiết là n ≤ 3.

Subtask 3 (20/70 điểm): Giả thiết là n ≤ 4.

Subtask 4 (20/70 điểm): Giả thiết là n ≤ 10.

Ví dụ:

Dữ liệu:

1

20 4 1

1 1

5 1

7 1

20 20

Kết quả

3