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 là số con đường trong thành phố. Tiếp theo là dòng, mỗi dòng chứa bốn số nguyên , cho biết có một con đường đi từ điểm tới điểm . Mọi con đường đều song song với trục hoặc trục , 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 : là toạ độ nhà của Peter và 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 .
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à hoặc ).
Ràng buộc
- .
- Giá trị tuyệt đối của mọi số nguyên trong dữ liệu nhỏ hơn .
- Mỗi con đường có độ dài dương ( hoặc , nhưng không cả hai).
- Tổng các trong một file không quá .
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 chia thành ô 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 . 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. |
https://oj.chuyentin.pro/problem/icpcwf05_f
Bình luận