Czech Technical University in Prague
Faculty of Mathematics and Physics, Charles University in Prague
Faculty of Electrical Engineering and Computer Science, Technical University of Ostrava
Faculty of Informatics and Information Technologies, Slovak University of Technology
acm
Faculty of Informatics, Masaryk University
cz
Faculty of Management Science and Informatics, University of Zilina
CTU Open Contest 2009
Robotic Rails
rr.c, rr.C, rr.java, rr.p
ACM recently presented their new programme to fight against corruption by employing robots in
various activities that have been performed by humans before, especially in the state machinery.
Robots have one big advantage -- it is practically impossible to bribe them, whatever amount
you offer.
Robots also have one big disadvantage -- someone must program them to do anything useful.
A robot without a program would only stand in the same place and never move.
Your task is to program a mechanical robot named Karel to allow him to move. Karel is situated
in a very large hall and it can move using a special system of rails, which are built in the floor.
The robot always moves across a single rail, which is so narrow that we can consider its width
being zero.
All rails are formed by straight segments, which may intersect with each other (or even overlap).
The robot can switch from one segment to another at any point they have in common. However,
due to some technical limitations, at any single point, the robot may never turn by more than
90 degrees. In other words, all angles on Karel's path must be obtuse.1
!!
If we look at the picture above, it is impossible to make a turn at the crossing marked by excla-
mation marks and Karel must use a longer path instead (dashed line). The picture corresponds
to the first scenario in Sample Input.
Your task is to find the shortest path for Karel to move from one position to another.
1
obtuse angle = tupy uhel / tupy uhol
´´
´
Input Specification
The input will consist of several test scenarios. Each scenario starts by a line with a single
positive integer R (1 R 100) -- the number of rail segments. Then there are R lines, each
containing four integers x1, y1, x2, y2 giving the coordinates of the endpoints of one segment.
You may assume that no coordinate will be less then -10000 or more than 10000 and that all
segments will have non-zero length.
The last scenario is followed by a line containing single zero.
Karel always starts at the first point given in the scenario (at the beginning of the first segment)
and is facing the direction of that first segment - therefore, its first movement must start either
in that direction or within an angle of 90 degrees.
The target point is the last point given in the input of that scenario (the end of the last segment).
You may assume these this point is always different from the start position. It is required that
Karel not only reaches the target point, but it must also remain standing in a correct direction
-- the direction of the last segment. Karel may either arrive there via that segment, or via
a different one but with a deviation no more than 90 degrees.
Output Specification
For each scenario, output one single number, rounded to exactly three digits after the decimal
point (there may be unnecessary zeros). The number must state the length of the shortest path
that satisfies all criteria described above. If it is not possible to reach the target point at all,
Sample Input
5
1
5
2
1
1
0
6
4
1
1
5
1
5
1
4
5
1
2
4
5
2
1
121
3
343
0
Output for Sample Input
9.541
unreachable