III Olympiad in Informatics 1995/1996
|
Task: ZAM
|
Author: Krzysztof Diks
|
I stage contest |
A group of explorers in quest of a treasure found a map of a castle. According to the map there is an invaluable treasure hidden in the cellar of the castle.
The map
is drawn on a square mesh,
which knots have integer coordinates. A left bottom corner (knot) has coordinates
(0, 0) and the opposite, right top, corner has coordinates (1000, 1000). The
plan of the castle has a shape
of the polygon and its sides cover the lines of the net. Two adjacent sides of
the polygon are
always perpendicular. A border of the polygon is a closed broken line, i.e. each of
its vertices belongs to two segments of a broken line and any other point
belongs to one segment.
Segments of lines of the net within a polygon as well as sides of the polygon show corridors
in the castle's cellar. There are two special knots of the polygon - one stands for an entrance, the other for the treasure.
We want to compute the length of the shortest route in the cellar from the entrance to
the treasure. We take as a unit the length of the side of a single square of the net.
10 9 6 9 2 12 2 12 9 2 9 2 1 8 1 8 3 4 3 4 6 11 5 3 1
In this case, the correct answer is the following text file ZAM.OUT:
14
Your program should look for the file ZAM.IN in the current directory and produce the output file ZAM.OUT in the current directory too. The file containing the source code of your program should have a name ZAM.???, whereas you should put three-letter abbreviation of the used programming language name instead of ???. The same program in executable form should be written in the file ZAM.EXE