Hide-and-seek
Time limit8sMemory limit512 MB
Given N line segments forming a connected network and a start point on it, find the maximum shortest-path distance along the segments from the start to any point.
- Level
Medium7 of 10
- Topics
- Graph, Shortest path, Geometry, Implementation
- Solved
- No attempts yet
Problem
Hide-and-seek is a children's game. One player is chosen as it, and the others hide here and there so that it cannot find them.
This time you played it and found all the other players. Now it is your turn to hide from it. Since you are tired of running around looking for people, you do not want to be it again. So you are going to hide at the place as far as possible from it. But where is that place?
Your task is to find the place and calculate the maximum possible distance from it to the place to hide.
Input
The input contains a number of test cases.
The first line of each test case contains a positive integer N (N ≤ 1000). The following N lines give the map where hide-and-seek is played. The map consists of N corridors. Each line contains four real numbers x1, y1, x2, and y2, where (x1, y1) and (x2, y2) indicate the two end points of the corridor. All corridors are straight, and their widths are negligible. After these N lines, there is a line containing two real numbers sx and sy, indicating the position of it. You can hide at an arbitrary place of any corridor, and it always walks along corridors. Numbers in the same line are separated by a single space.
It is guaranteed that it's starting position (sx, sy) is located on some corridor and linked to all corridors directly or indirectly.
The end of the input is indicated by a line containing a single zero.
Output
For each test case, output a line containing the distance along the corridors from it's starting position to the farthest position. The value may contain an error less than or equal to 0.001. You may print any number of digits below the decimal point.