Hàng rào chống hươu
Đề bài
Mô tả
Bác Magnus đã trồng một số cây non trong trang trại của mình, như một phần của dự án trồng lại rừng. Không may, hươu rất thích ăn chồi và lá non của cây con, nên cần dựng hàng rào bảo vệ quanh chúng. Vì hươu và những con vật thích gặm cây khác có thể vươn qua một phần hàng rào, mọi hàng rào phải cách mỗi cây non ít nhất một khoảng tối thiểu (gọi là lề).
Hàng rào chống hươu khá đắt, nên bác Magnus muốn tổng chiều dài hàng rào sử dụng là nhỏ nhất. Nhiệm vụ của bạn là viết chương trình tính tổng chiều dài hàng rào nhỏ nhất cần dùng để bao quanh và bảo vệ các cây non. Hàng rào có thể gồm cả đoạn thẳng lẫn đoạn cong. Bạn có thể thiết kế một hàng rào duy nhất bao quanh tất cả các cây non, hoặc nhiều hàng rào, mỗi hàng rào bao quanh một nhóm cây non riêng.
Hình 1 cho hai cấu hình ví dụ, mỗi cấu hình gồm ba cây non với lề khác nhau. Ở cấu hình phía trên, ứng với bộ test thứ nhất của ví dụ 1, cách tốt nhất gồm hai hàng rào riêng biệt. Ở cấu hình phía dưới, ứng với bộ test thứ hai của ví dụ 1, cách tốt nhất chỉ gồm một hàng rào.

Hình 1: Hàng rào chống hươu (trên: lề , dưới: lề ).
Dữ liệu vào
Dữ liệu vào gồm nhiều bộ test. Dòng đầu tiên của mỗi bộ test chứa hai số nguyên là số cây non và là lề cần có quanh mỗi cây non. Tiếp theo là dòng, mỗi dòng chứa hai số nguyên và là tọa độ Descartes của một cây non. Không có hai cây non nào ở cùng một vị trí. Để đơn giản, có thể coi mỗi cây non là một điểm và độ dày của hàng rào bằng .
Sau bộ test cuối cùng là một dòng chứa hai số .
Dữ liệu ra
Với mỗi bộ test, in ra số thứ tự của bộ test (bắt đầu từ ) và tổng chiều dài nhỏ nhất của hàng rào cần dùng để bảo vệ các cây non với lề đã cho, làm tròn tới đúng hai chữ số sau dấu thập phân. Làm theo đúng định dạng trong ví dụ.
Ràng buộc
- , .
- , .
- Mỗi file có không quá bộ test.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 2 0 0 2 0 10 0 3 4 0 0 2 0 10 0 0 0 |
Case 1: length = 29.13 Case 2: length = 45.13 |
Bộ 1 (Hình 1, trên): một hàng rào quanh hai cây , dài , một hàng rào tròn quanh cây dài , tổng . Bộ 2 (Hình 1, dưới): một hàng rào quanh cả ba cây dài . |
| 1 5 0 0 4 5 0 0 10 0 0 100 10 100 3 10 -5 0 0 0 5 0 0 0 |
Case 1: length = 31.42 Case 2: length = 102.83 Case 3: length = 82.83 |
Bộ 1: một cây, hàng rào là đường tròn bán kính , dài . Bộ 2: hai hàng rào, mỗi hàng rào quanh hai cây cùng hàng, mỗi cái dài . Bộ 3: một hàng rào quanh ba cây thẳng hàng, dài . |
Bình luận