아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

포물선 순간이동 장치

시간 제한2초메모리 제한128 MB

요약
무한 속도로 이동할 수 있는 포물선 호가 최대 100개 주어질 때, 점 V에서 점 W까지 걸리는 최소 시간을 구한다.
난이도

보통10점 중 6점

유형
기하, 그래프, 최단 경로
정답자
아직 제출이 없습니다

문제

플랫랜드는 직교좌표계 OxyOxy를 갖는 평면입니다. 이곳의 주민들은 속도 11로 움직이는 점이므로, 점 VV에서 점 WW까지 이동하는 최소 시간은 선분 VWVW의 길이와 같습니다. 플랫랜드의 학교에서는 이를 "최단 경로 정리"라고 가르칩니다.

포물선 순간이동 장치가 발명되면서 이 정리는 더 이상 성립하지 않게 되었습니다. 포물선 순간이동 장치는 무한한 속도로 이동할 수 있는 포물선의 연속된 한 조각으로, 같은 장치 위의 두 점 사이는 00의 시간에 이동할 수 있습니다.

장치에 속하는 점 (x,y)(x, y)는 XL≤x≤XRX_L \le x \le X_R 범위에서 y=Ax2+Bx+Cy = A x^2 + B x + C를 만족합니다. 여기서 AA, BB, CC, XLX_L, XRX_R은 장치의 매개변수입니다.

현재 NN개의 장치가 설치되어 있습니다. 두 점 VV와 WW가 주어질 때, 이 장치들을 이용하여 VV에서 WW까지 이동하는 데 필요한 최소 시간을 구하세요. 주민은 임의의 두 점 사이를 속도 11의 직선으로 걸을 수 있으며, 어떤 장치든 그 위의 임의의 점에서 비용 없이 올라타거나 내릴 수 있습니다.

입력

첫째 줄에 장치의 개수 NN (0≤N≤1000 \le N \le 100)이 주어집니다. 둘째 줄에 출발점 VV의 좌표인 두 정수 XVX_V와 YVY_V (−100≤XV≤100-100 \le X_V \le 100, −106≤YV≤106-10^6 \le Y_V \le 10^6)가 주어집니다. 셋째 줄에 도착점 WW의 좌표인 두 정수 XWX_W와 YWY_W (−100≤XW≤100-100 \le X_W \le 100, −106≤YW≤106-10^6 \le Y_W \le 10^6)가 주어집니다.

이어지는 NN개의 줄에는 각각 ii번째 장치를 나타내는 다섯 정수 AiA_i, BiB_i, CiC_i, XLiX_{Li}, XRiX_{Ri}가 공백으로 구분되어 주어집니다 (−100≤Ai,Bi,Ci≤100-100 \le A_i, B_i, C_i \le 100, Ai≠0A_i \ne 0, −100≤XLi<XRi≤100-100 \le X_{Li} < X_{Ri} \le 100).

출력

VV에서 WW까지 이동하는 최소 시간을 소수점 아래 정확히 44자리로 반올림하여 한 줄에 출력하세요.

예제3

  1. 예제 1

    입력
    2
    0 10
    0 -10
    1 0 0 -10 10
    -1 0 0 -10 10
    
    예상 출력
    6.2450
    
  2. 예제 2

    입력
    0
    0 0
    3 4
    
    예상 출력
    5.0000
    
  3. 예제 3

    입력
    1
    0 0
    0 100
    1 0 0 -10 10
    
    예상 출력
    9.9875