숨바꼭질
시간 제한8초메모리 제한512 MB
연결된 N개의 선분 네트워크와 그 위의 시작점이 주어질 때, 시작점에서 선분을 따라 이동하는 최단 거리가 가장 먼 지점까지의 거리를 구한다.
문제
숨바꼭질은 아이들의 놀이이다. 술래를 정하고, 나머지 사람들은 여기저기 숨어서 술래가 찾지 못하게 한다.
이번에는 술래를 맡아서 다른 사람을 모두 찾았다. 이제는 술래에게서 숨을 차례이다. 여기저기 돌아다니며 사람을 찾느라 지쳤기 때문에, 다시 술래를 하고 싶지 않다. 그래서 술래에게서 최대한 멀리 떨어진 곳에 숨으려고 한다. 그런데 그곳은 어디일까?
술래에게서 가장 멀리 떨어진 곳을 찾고, 그곳까지의 최대 거리를 계산하는 것이 문제이다.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다.
각 테스트 케이스의 첫째 줄에는 양의 정수 N이 주어진다 (N ≤ 1000). 다음 N개의 줄에는 숨바꼭질을 하는 지도의 정보가 주어진다. 지도는 N개의 복도로 이루어져 있다. 각 줄에는 네 개의 실수 x1, y1, x2, y2가 주어지며, (x1, y1)과 (x2, y2)는 복도의 양 끝점을 나타낸다. 모든 복도는 직선이고, 복도의 폭은 무시할 수 있을 만큼 좁다. 이 N개의 줄 다음에는 두 개의 실수 sx, sy가 주어지며, 이는 술래의 위치를 나타낸다. 숨는 사람은 아무 복도의 임의의 위치에 숨을 수 있고, 술래는 항상 복도를 따라 걷는다. 같은 줄에 있는 수들은 하나의 공백으로 구분된다.
술래의 시작 위치 (sx, sy)는 어떤 복도 위에 있고, 모든 복도와 직접 또는 간접적으로 연결되어 있음이 보장된다.
입력의 끝은 하나의 0만 포함하는 줄로 나타낸다.
출력
각 테스트 케이스에 대해, 술래의 시작 위치에서 복도를 따라 가장 먼 위치까지의 거리를 한 줄에 출력한다. 값의 오차는 0.001 이하이면 된다. 소수점 아래 자릿수는 얼마든지 출력해도 된다.