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

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

100미터 달리기

면접 대비

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

요약
타임스탬프가 있는 GPS 좌표들이 주어지고 구간마다 속도가 일정할 때, 달린 경로를 따라 정확히 100미터를 지나는 최소 시간을 구한다.
난이도

보통10점 중 7점

유형
투 포인터, 기하, 수학, 구현
정답자
아직 제출이 없습니다

문제

CS 학생인 우리는 하루 종일 앉아서 화면만 본다. 이는 여러모로 몸에 나쁘다. 허리 통증, 안경 착용, 사회생활 부족. 정부에 따르면 규칙적인 운동이 이런 문제 일부를 완화하는 데 도움이 된다. 당신은 이것이 사실이 아닐 수도 있다고 굳게 믿지만, 달리기를 시작하고 Ztrawa GPS 추적 모바일 앱으로 달리기를 기록하기로 했다.

Ztrawa는 당신의 위치 좌표 (x,y)(x, y)를 임의의 간격으로 저장한다. 달리기가 끝나면 고도 상승량, 가장 빠른 100100m, AA 지점에서 BB 지점까지의 평균 속도 등 여러 가지 멋진 통계를 볼 수 있다.

모든 CS 학생이 Min-Max를 좋아하듯, 당신은 달리기 전체에서 최고 기록인 100100m에만 관심이 있다. 안타깝게도 Ztrawa 앱에 버그가 있어 Min-Max 기능이 작동을 멈췄으므로 직접 계산해야 한다.

Ztrawa는 유한한 개수의 데이터 포인트만 수집하므로, 연속한 두 데이터 포인트 사이에서는 속도가 일정하다고 가정한다. 예를 들어, 400400m 트랙을 달리며 트랙을 한 바퀴 돌아 출발점으로 돌아오는 동안 66개의 데이터 포인트를 기록했다고 하자. 이것이 예제 1이며, 왼쪽 아래에서 달리기를 시작해 반시계 방향으로 돌았다.

가장 빠른 100100m가 몇 초였는지 구하는 프로그램을 직접 작성해야 한다.

예제 1의 그림.

입력

첫째 줄에 Ztrawa의 측정값 개수를 나타내는 정수 1≤n≤1051 \leq n \leq 10^5가 주어진다. 이어서 nn개의 줄에 각 측정값의 정보가 주어진다. ii번째 줄에는 세 실수 xix_i, yiy_i, tit_i가 주어지며, 이는 측정값 ii 시점에 당신이 출발점을 기준으로 한 미터 좌표 (xi,yi)(x_i, y_i)에 있었고 세션 시작 후 tit_i초가 지났음을 의미한다. 모든 ii에 대해 −105≤xi,yi≤105-10^5 \leq x_i, y_i \leq 10^5이고 0<t1<t2<…<tn≤1070 < t_1 < t_2 < \ldots < t_n \leq 10^7이다. 모든 실수는 소수점 이하 최대 66자리까지 주어진다.

당신은 항상 시간 00에 (0,0)(0, 0)에서 달리기를 시작한다.

출력

가장 빠른 100m를 달린 시간을 초 단위로 나타내는 실수 하나를 출력한다. 절대 오차 또는 상대 오차가 10−410^{-4} 이하이면 정답으로 인정된다.

예제1

  1. 예제 1

    입력
    6
84.39 0 10
120.89 36.5 14.3
84.39 73 18.4
0 73 28.5
-36.5 36.5 32.7
0 0 36.95
    예상 출력
    8.130299066033297