trang chủ / đề bài / icpcwf05_f

Băng qua đường

Đề bài

Mô tả

Peter Longfoot là sinh viên trường đại học Suburbia. Mỗi sáng Peter rời nhà đi bộ tới trường. Nhiều sinh viên khác lái ô tô hoặc đạp xe tới trường, nhưng Peter thích đi bộ hơn, tránh dòng xe cộ hỗn loạn của thành phố nhiều nhất có thể.

Tiếc là Peter không thể tránh hoàn toàn xe cộ, vì anh phải băng qua các con đường để tới trường. Gần đây Peter tự hỏi làm sao để số con đường phải băng qua là ít nhất. Chẳng hạn, trên bản đồ dưới đây các con đường được vẽ bằng các đường thẳng nằm ngang và thẳng đứng. Để đi từ nhà (Home) tới trường (University), Peter phải băng qua ít nhất hai con đường. Peter không được băng qua một cặp đường tại giao điểm của chúng và không được đi dọc theo một con đường.

Trong hình, các con đường là các đoạn thẳng, các mũi tên là những cách đi có thể của Peter. Các mũi tên đen là một cách đi chỉ phải băng qua hai con đường. Các mũi tên xám là một cách đi phải băng qua bốn con đường. Cách đi bằng các mũi tên nét đứt ("Not an allowed Path") không hợp lệ vì nó băng qua hai con đường tại giao điểm của chúng. Hình này ứng với thành phố thứ nhất của ví dụ 1.

Peter biết vị trí mọi con đường trong thành phố, nhưng anh gặp khó khăn khi tìm đường đi tốt nhất tới trường. Hãy viết chương trình giúp anh.

Dữ liệu vào

Dữ liệu gồm nhiều mô tả thành phố. Mỗi mô tả bắt đầu bằng một dòng chứa một số nguyên n là số con đường trong thành phố. Tiếp theo là n dòng, mỗi dòng chứa bốn số nguyên x1,y1,x2,y2, cho biết có một con đường đi từ điểm (x1,y1) tới điểm (x2,y2). Mọi con đường đều song song với trục x hoặc trục y, vì thành phố được xây trên một lưới ô vuông. Các con đường có thể chồng lên nhau, khi đó chúng chỉ được tính là một con đường. Mô tả thành phố kết thúc bằng một dòng chứa bốn số nguyên xh,yh,xu,yu: (xh,yh) là toạ độ nhà của Peter và (xu,yu) là toạ độ trường đại học. Nhà của Peter và trường đại học không nằm trên con đường nào.

Hãy coi các con đường là các đoạn thẳng, tức là con đường không có bề rộng. Dù các đầu mút của con đường là số nguyên, Peter không cần đi theo các đường lưới: anh có thể đi theo bất kỳ hướng nào anh muốn.

Dữ liệu kết thúc bằng một dòng chứa số nguyên 0.

Dữ liệu ra

Với mỗi mô tả thành phố, đầu tiên in số thứ tự của nó trong dãy mô tả. Sau đó in số con đường ít nhất mà Peter phải băng qua để đi từ nhà tới trường đại học. Theo đúng định dạng trong ví dụ (luôn viết streets, kể cả khi số con đường là 0 hoặc 1).

Ràng buộc

  • 1≤n≤500.
  • Giá trị tuyệt đối của mọi số nguyên trong dữ liệu nhỏ hơn 2·109.
  • Mỗi con đường có độ dài dương (x1=x2 hoặc y1=y2, nhưng không cả hai).
  • Tổng các n trong một file không quá 5000.

Ví dụ

Input Output Giải thích
8
6 0 24 0
24 0 24 4
24 4 6 4
6 4 6 0
12 1 26 1
26 1 26 6
26 6 12 6
12 6 12 1
0 1 17 3
1
10 10 20 10
1 1 30 30
0
City 1
Peter has to cross 2 streets
City 2
Peter has to cross 0 streets
Thành phố 1 là hình trên: trường nằm trong cả hai hình chữ nhật nên phải băng qua hai cạnh. Thành phố 2 chỉ có một con đường, Peter đi vòng qua đầu mút của nó.
9
2 0 2 6
4 0 4 6
0 2 6 2
0 4 6 4
0 0 4 0
2 0 6 0
6 0 6 6
6 6 0 6
0 6 0 0
3 3 1 1
6
0 0 4 0
0 0 0 4
0 4 4 4
4 4 4 0
1 0 3 0
4 0 4 4
2 2 2 -3
1
0 0 0 5
1 1 1 1
0
City 1
Peter has to cross 2 streets
City 2
Peter has to cross 1 streets
City 3
Peter has to cross 0 streets
Ví dụ tự thêm. Thành phố 1: hình vuông 6×6 chia thành 9 ô bởi hai đường dọc và hai đường ngang (cạnh dưới cho bởi hai đoạn chồng lên nhau); đi từ ô giữa tới ô góc phải qua hai đường, không được cắt chéo qua giao điểm (2,2). Thành phố 2: cạnh dưới và cạnh phải của hình vuông được cho nhiều lần nhưng chỉ tính là một con đường. Thành phố 3: nhà trùng với trường.

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