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

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

이민

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

요약
피터가 x축을 따라 이동하며 n번 속도가 바뀌는 물체를 추적할 때, t0 이후 시선 각속도의 최댓값을 구한다.
난이도

어려움10점 중 8점

유형
기하, 수학, 구현, 이분 탐색
정답자
아직 제출이 없습니다

문제

피터 피그는 트랙터를 타고 시각 00에 원점에서 출발해 xx축을 따라 속력 uu로 움직인다. 도로가 무한하고 볼거리가 없어서 피터는 재미를 찾고 있다. 시각 t0t_0에 그는 점 (x0,y0)(x_0, y_0)에 있는 어떤 물체가 속도 v0=(v0x,v0y)v_0 = (v_{0x}, v_{0y})로 움직이는 것을 발견한다. 그래서 피터는 물체를 계속 바라보면서 고개를 돌리기 시작한다. 때때로 (총 nn번), 물체는 속도를 바꾼다. 즉, 시각 tit_i에 물체는 속도를 순간적으로 vi=(vix,viy)v_i = (v_{ix}, v_{iy})로 바꾼다 (i=1,2,…,ni = 1, 2, \ldots, n). 물체는 피터와 절대 충돌하지 않는다.

f(t)f(t)를 시각 tt에 피터에서 물체로 향하는 방향과 xx축 사이의 방향각(라디안)으로 정의하자. 함수 f(t)f(t)가 연속이기만 하면 f(t)f(t)가 실제 각도와 2π2 \pi의 배수만큼 달라도 허용한다. 피터 머리의 각속도를 도함수 f′(t)f'(t)로 정의한다. 시각 t0t_0부터 무한대까지 ∣f′(t)∣|f'(t)|의 최댓값을 구해야 한다. 다시 말해, 각속도의 절댓값의 최댓값을 구해야 한다. 답은 유한하다.

입력

첫째 줄에는 네 정수 uu, x0x_0, y0y_0, nn이 주어진다 (1≤u≤1001 \le u \le 100, ∣x0∣,∣y0∣≤108|x_0|, |y_0| \le 10^8, 0≤n≤1050 \le n \le 10^5). 이는 피터의 트랙터 속력, 피터가 처음 발견했을 때 물체의 좌표, 물체가 속도를 바꾸는 횟수이다.

다음 (n+1)(n + 1)개 줄에는 각각 공백으로 구분된 세 정수 tit_i, vixv_{ix}, viyv_{iy}가 주어진다 (0≤ti≤1060 \le t_i \le 10^6, ∣vix∣,∣viy∣≤100|v_{ix}|, |v_{iy}| \le 100). t0<t1<…<tnt_0 < t_1 < \ldots < t_n이다. (vix,viy)=(0,0)(v_{ix}, v_{iy}) = (0, 0)일 수도 있다. 또한 시각 tnt_n 이후 물체의 움직임은 무한히 이어진다.

출력

피터가 물체를 관찰하는 동안 피터 머리의 각속도의 절댓값의 최댓값을 한 줄에 실수 하나로 출력한다. 절대 오차 또는 상대 오차는 10−610^{-6}을 넘지 않아야 한다.

예제2

  1. 예제 1

    입력
    1 0 -2 0
    0 1 0
    
    예상 출력
    0.0000000000
    
  2. 예제 2

    입력
    2 0 -2 0
    0 3 1
    
    예상 출력
    1.0000000000