| About Olympic -> Problems |  |
|
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.
Task
Write a program that:- reads from the text file ZAM.IN the following information about the
castle:
- the number of vertices of the polygon representing the castle, 4 <= n <= 5000,
- the coordinates of the vertices in the order generated while traversing the edge of the polygon,
- the coordinates of the entrance and the treasure;
- computes the length of the shortest route (over the lines of the net) from the entrance to the treasure;
- writes the result in the text file ZAM.OUT.
Input
In the first line of the text file ZAM.IN, there is written one integer n from the interval [4..5000] - this is the number of vertices of the polygon representing the castle. In each of the following n lines of the input file, there are written two integers from the interval [0..10000] separated by a single space; these are the coordinates of the successive vertex of the polygon. Then, in the second last line of the input file there are written the coordinates of the entrance, and in the last line - the coordinates of the treasure. The last two pairs of coordinates are written in the same format as the previous ones.Output
In the only line of the text file ZAM.OUT one integer should be written - the length of the shortest route from the entrance to the treasure.Example
The description of the castle from the picture is written in the following text file ZAM.IN: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