Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

DHGARDEN - Vườn cây

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 ≤ 109; 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 điểm): Giả thiết là n ≤ 2.
Subtask 2 (15 điểm): Giả thiết là n ≤ 3.
Subtask 3 (20 điểm): Giả thiết là n ≤ 4.
Subtask 4 (20 điểm): Giả thiết là n ≤ 10.

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


Được gửi lên bởi:Lê Đôn Khuê
Ngày:2014-04-20
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:HSG Duyên hải và Đồng bằng Bắc Bộ

hide comments
2014-05-28 15:21:07 Nắng
@Phantom làm ở nhà thì bạn nên làm cách tối ưu :)
2014-05-27 11:03:27 Lollipop
Thử chắc sub1 sub 2 được 50 :D

Last edit: 2014-05-27 11:06:04
2014-04-21 10:32:59 zai zai
lam mai moi AC duoc 1 bai @.@
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.