포물선 순간이동 장치
시간 제한2초메모리 제한128 MB
무한 속도로 이동할 수 있는 포물선 호가 최대 100개 주어질 때, 점 V에서 점 W까지 걸리는 최소 시간을 구한다.
문제
플랫랜드는 직교좌표계 를 갖는 평면입니다. 이곳의 주민들은 속도 로 움직이는 점이므로, 점 에서 점 까지 이동하는 최소 시간은 선분 의 길이와 같습니다. 플랫랜드의 학교에서는 이를 "최단 경로 정리"라고 가르칩니다.
포물선 순간이동 장치가 발명되면서 이 정리는 더 이상 성립하지 않게 되었습니다. 포물선 순간이동 장치는 무한한 속도로 이동할 수 있는 포물선의 연속된 한 조각으로, 같은 장치 위의 두 점 사이는 의 시간에 이동할 수 있습니다.
장치에 속하는 점 는 범위에서 를 만족합니다. 여기서 , , , , 은 장치의 매개변수입니다.
현재 개의 장치가 설치되어 있습니다. 두 점 와 가 주어질 때, 이 장치들을 이용하여 에서 까지 이동하는 데 필요한 최소 시간을 구하세요. 주민은 임의의 두 점 사이를 속도 의 직선으로 걸을 수 있으며, 어떤 장치든 그 위의 임의의 점에서 비용 없이 올라타거나 내릴 수 있습니다.
입력
첫째 줄에 장치의 개수 ()이 주어집니다. 둘째 줄에 출발점 의 좌표인 두 정수 와 (, )가 주어집니다. 셋째 줄에 도착점 의 좌표인 두 정수 와 (, )가 주어집니다.
이어지는 개의 줄에는 각각 번째 장치를 나타내는 다섯 정수 , , , , 가 공백으로 구분되어 주어집니다 (, , ).
출력
에서 까지 이동하는 최소 시간을 소수점 아래 정확히 자리로 반올림하여 한 줄에 출력하세요.