trang chủ / đề bài / icpcwf04_h

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 50 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 25 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 n (1≤n≤100) là số con phố trên bản đồ. Mỗi dòng trong n 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 x1, y1, x2, y2: con phố đi từ điểm (x1,y1) đến điểm (x2,y2). Toạ độ tính bằng mét, 0≤x1,y1,x2,y2≤100000.

Sau bản đồ cuối cùng là một dòng chứa số 0.

Dữ liệu ra

Với mỗi bản đồ, in số thứ tự của bản đồ (bắt đầu từ 1) 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

  • 1≤n≤100; 0≤x1,y1,x2,y2≤100000.
  • 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 25 mét: hiệu giữa khoảng cách đó và bội của 25 gần nhất ít nhất là 0,001 mét.
  • Mỗi file có không quá 100 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 (60,5; 2) và cắt con phố y=1 tại x=30,25 và x=90,75. Con phố y=1 trồng được 3 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 30,27 mét, không trồng được cây nào vì phải cách cả hai giao lộ ít nhất 25 mét; mỗi đoạn còn lại trồng được một cây. Tổng cộng 3+2+2=7.
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 50,8 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ố y=10 từ x=0 đến 70 bị cắt tại x=10,30,60 thành các đoạn dài 10,20,30,10 nên không trồng được cây nào; con phố từ (80,10) đến (151,10) cùng nằm trên đường thẳng đó nhưng không giao với con phố nào, trồng được 2 cây; con phố x=10 trồng 1 cây, con phố x=30 không trồng được cây nào, con phố x=60 trồng 3 cây (đoạn dài 151 mét sau giao lộ).

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0