Những con phố rợp bóng cây
Đề bài
Mô tả
Hội đồng thành phố Greenville vừa biểu quyết cải thiện diện mạo các con phố trong nội thành. Để thành phố có thêm màu xanh, hội đồng quyết định trồng cây dọc theo tất cả các con phố và đại lộ chính. Để ước lượng chi phí của dự án, hội đồng muốn biết sẽ trồng được bao nhiêu cây. Việc trồng cây bị giới hạn bởi hai quy định:
- Dọc theo một con phố, hai cây phải cách nhau ít nhất mét. Quy định này bảo đảm cây có đủ chỗ để lớn và giữ chi phí dự án trong giới hạn hợp lý.
- Vì lý do an toàn, không cây nào được trồng cách giao lộ gần nhất ít hơn mét (khoảng cách tính dọc theo con phố). Quy định này giúp người tham gia giao thông dễ dàng nhìn thấy nhau khi tiến tới giao lộ.
Mọi con phố trong dự án đều thẳng, không có khúc rẽ hay khúc cong. Hai quy định trên chỉ áp dụng cho các cây trên cùng một con phố; điểm đầu mút của một con phố không phải là giao lộ.
Hội đồng cần biết số cây nhiều nhất có thể trồng mà vẫn tuân thủ hai quy định trên.
Dữ liệu vào
Dữ liệu gồm mô tả của nhiều bản đồ phố. Dòng đầu tiên của mỗi bản đồ chứa số nguyên () là số con phố trên bản đồ. Mỗi dòng trong dòng tiếp theo mô tả một con phố là một đoạn thẳng trên mặt phẳng toạ độ, gồm bốn số nguyên , , , : con phố đi từ điểm đến điểm . Toạ độ tính bằng mét, .
Sau bản đồ cuối cùng là một dòng chứa số .
Dữ liệu ra
Với mỗi bản đồ, in số thứ tự của bản đồ (bắt đầu từ ) rồi in số cây nhiều nhất có thể trồng, đúng theo định dạng ở ví dụ: dòng Map k rồi dòng Trees = t.
Ràng buộc
- ; .
- Mỗi con phố có độ dài dương.
- Mỗi điểm đầu mút nằm trên đúng một con phố (là con phố của chính nó). Nói riêng, không có hai con phố nào chồng lên nhau.
- Tại mỗi giao lộ có đúng hai con phố gặp nhau.
- Trên mỗi con phố, khoảng cách giữa hai điểm liền kề (giao lộ hoặc đầu mút của con phố) không phải là bội chính xác của mét: hiệu giữa khoảng cách đó và bội của gần nhất ít nhất là mét.
- Mỗi file có không quá bản đồ.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 3 0 40 200 40 40 0 40 200 0 200 200 0 4 0 30 230 30 0 200 230 200 30 0 30 230 200 0 200 230 3 0 1 121 1 0 0 121 4 0 4 121 0 0 |
Map 1 Trees = 13 Map 2 Trees = 20 Map 3 Trees = 7 |
Bản đồ 3: hai đường chéo cắt nhau tại và cắt con phố tại và . Con phố trồng được cây (mỗi đoạn một cây). Trên mỗi đường chéo, đoạn giữa hai giao lộ dài khoảng mét, không trồng được cây nào vì phải cách cả hai giao lộ ít nhất mét; mỗi đoạn còn lại trồng được một cây. Tổng cộng . |
| 1 0 0 30 41 2 100000 0 100000 49 0 100000 1 100000 5 0 10 70 10 10 0 10 70 80 10 151 10 30 0 30 30 60 0 60 161 0 |
Map 1 Trees = 2 Map 2 Trees = 2 Map 3 Trees = 6 |
Ví dụ tự thêm. Bản đồ 1: con phố dài khoảng mét, không có giao lộ, trồng ở hai đầu. Bản đồ 2: mỗi con phố một cây. Bản đồ 3: con phố từ đến bị cắt tại thành các đoạn dài nên không trồng được cây nào; con phố từ đến cùng nằm trên đường thẳng đó nhưng không giao với con phố nào, trồng được cây; con phố trồng cây, con phố không trồng được cây nào, con phố trồng cây (đoạn dài mét sau giao lộ). |
https://oj.chuyentin.pro/problem/icpcwf04_h
Bình luận