과속카메라

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

요약

일정한 속도로 움직이는 차량의 시각별 위치 구간 N개가 주어질 때, 모든 구간과 모순되지 않는 최소 속도와 최대 속도를 구한다.

난이도: 보통10점 중 7점
유형: 수학, 이분 탐색, 그리디
정답자: 아직 제출이 없습니다

문제

UNIST 근처의 직선 고속도로에는 과속 차량을 감지하기 위한 과속카메라가 있다. 이 과속카메라는 다음과 같은 원리로 차량의 속도를 측정한다.

차량이 감지 범위 내에 진입하면, $N$ 개의 서로 다른 시각에 차량의 위치를 촬영한다. 이 과속카메라는 움직이는 물체의 정확한 위치를 측정하지는 못하지만, 각 사진마다 차량의 좌표 범위를 알 수 있다. $i$ 번째 사진은 차량의 좌표가 $l\_i$ 이상 $r\_i$ 이하라는 정보를 담고 있다. 과속카메라는 촬영한 $N$ 장의 사진 정보를 통해서 차량의 최소 속도와 최대 속도를 계산할 수 있다. 측정하는 동안 차량의 속도는 항상 일정하다고 가정하며, 속도는 음수가 될 수도 있다.

어느 날, 고속도로를 신나게 달리던 윤이는 과속카메라에 자신이 찍힌 것을 발견했다. 벌금이 두려웠던 윤이는 과속카메라를 해킹해서 촬영된 사진들과 과속카메라 소프트웨어를 지워버렸다. 당신의 목표는 과속카메라가 정상 작동할 수 있도록 과속카메라의 소프트웨어를 복원하는 것이다.

입력

첫 번째 줄에 과속카메라가 찍은 사진의 수 $N$ 이 주어진다. $(2\le N\le 300\ 000)$

다음에 $N$ 개의 줄이 주어진다. 이 중 $i$ 번째 줄에는 세 정수 $t\_i$ , $l\_i$ , $r\_i$ 가 주어진다. $i$ 번째 사진이 찍힌 시각은 $t\_i$ 이며, 사진에서 차량의 좌표 범위가 $\[l\_i,r\_i]$ 임을 나타낸다. $t\_i$ 는 증가하도록 주어진다. $(0\le t\_i\le 10^9,0\le l\_i\le r\_i\le 10^9)$

항상 답이 존재하는 입력만 주어진다.

출력

과속카메라가 측정한 차량의 최소 속도와 최대 속도를 공백으로 구분하여 출력한다. 절대/상대 오차는 $10^{-6}$ 까지 허용한다.

예제1

예제 1
입력
```
3
0 10 40
4 60 90
8 30 200
```
예상 출력
```
5.00 20.00
```