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

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

자전거 경주

면접 대비

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

요약
각 자전거 선수가 위치 x_i에서 일정한 속도 v_i로 달릴 때, 선두와 후미 사이 거리가 가장 작아지는 시각 t와 그 거리를 구한다.
난이도

보통10점 중 6점

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

문제

도로 자전거 경주에 참가한 선수들이 시작 시각에 출발 지점으로부터 x1,x2,…,xnx_1, x_2, \ldots, x_n미터 떨어진 지점에 있다(nn은 선수의 수). 각 선수는 일정한 속력 v1,v2,…,vnv_1, v_2, \ldots, v_n미터/초로 달린다. 모든 선수는 같은 방향으로 달린다.

경주 상황을 취재하는 기자는 선두 선수와 최후미 선수 사이의 거리가 최소가 되는 순간을 알아내려 한다. 그때 헬리콥터에서 경주 참가자 전원을 한 번에 촬영하려고 한다.

선수의 수 nn, 시작 시각의 위치 x1,x2,…,xnx_1, x_2, \ldots, x_n, 속력 v1,v2,…,vnv_1, v_2, \ldots, v_n이 주어졌을 때, 선두 선수와 최후미 선수 사이의 거리 ll이 최소가 되는 시각 tt를 계산하는 프로그램을 작성하시오.

입력

첫째 줄에는 선수의 수 nn이 정수로 주어진다.

다음 nn개 줄에는 정수 두 개씩 주어진다. xix_i는 시작 시각에 ii번째 선수가 출발 지점에서 떨어진 거리이고(0≤xi≤1070 \le x_i \le 10^7), viv_i는 그 선수의 속력이다(0≤vi≤1070 \le v_i \le 10^7).

출력

두 실수를 출력한다. tt는 시작 시각부터 선두 선수와 최후미 선수 사이의 거리가 최소가 되는 순간까지 흐른 시간(초)이고, ll은 그때의 거리(미터)이다.

tt와 ll의 절대 오차 또는 상대 오차는 10−610^{-6} 이하여야 한다. 출력한 수를 xx, 정답을 yy라고 할 때 ∣x−y∣/max⁡{1,∣y∣}|x - y| / \max\{1, |y|\}의 값이 10−610^{-6}을 넘지 않으면 정답으로 인정한다.

제한

2≤n≤1052 \le n \le 10^5.

예제2

  1. 예제 1

    입력
    3
    0 40
    30 10
    40 30
    
    예상 출력
    1 30
    
  2. 예제 2

    입력
    5
    90 100
    100 70
    100 70
    110 60
    120 35
    
    예상 출력
    0.5 5.000000000000