구간 단속 종료 지점입니다

면접 대비

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

요약

속력이 M 이하로 제한된 차가 각 구간 [s_i, e_i)에서 평균 속도 v_i를 넘지 않아야 할 때, x=0에서 x=E까지 가는 최소 시간을 구한다.

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

문제

2025 아주대학교 프로그래밍 경시대회가 끝난 후, 현빈이는 차를 타고 본가에 내려가는 중이다.

현빈이가 본가로 가는 경로는 일직선으로 나타낼 수 있으며, 학교는 $x=0$ 에, 본가는 $x=E$ 에 위치하고 있다. 현빈이가 운전하는 차의 속력은 $M$ 을 넘을 수 없다.

본가로 향하는 길에는 총 $N$ 개의 구간 단속 지점이 있다. $i(1\leq i\leq N)$ 번째 구간 단속 지점 $\[s\_i,e\_i)$ 는 $x=s\_i$ 에서 시작하고 $x=e\_i$ 에서 종료되며, 구간을 지나는 평균 속도는 $v\_i$ 를 초과해서는 안 된다.

학교의 위치인 $x=0$ 에서 출발하여 현빈이의 본가인 $x=E$ 에 도착하는데 걸린 최소 시간을 구해보자.

단, 현빈이의 차가 가속과 감속을 하는 데는 시간이 걸리지 않는다.

입력

첫 번째 줄에 구간 단속 지점의 수 $N$ , 현빈이가 운전하는 차의 최대 속력 $M$ , 현빈이의 본가 위치 $E$ 가 공백으로 구분되어 주어진다. $(1\leq N\leq 500\\,000;$ $1\leq M \leq 1\\,235;$ $1 \leq E \leq 10^{9})$

두 번째 줄부터 $N$ 개 줄에 걸쳐 구간 단속 지점에 대한 정보 $s\_i, e\_i, v\_i$ 가 공백으로 구분되어 주어진다. $(0\leq s\_i < e\_i \leq E;$ $1\leq v\_i \leq M)$

입력으로 주어지는 모든 수는 정수이다.

출력

현빈이가 본가에 도착하는데 걸린 최소 시간을 출력한다. 절대/상대 오차는 $10^{-6}$ 까지 허용한다.

힌트

$x=s$ 를 통과하는 시점이 $t\_1$ 이고 $x=e$ 를 통과하는 시점이 $t\_2$ 라고 할 때, 구간 $\[s,e)$ 의 평균 속도 $\bar{v}$ 는 다음과 같다. $\bar{v}=\frac{e-s}{t\_2-t\_1}$
현빈이의 집은 용인시 수지구로, 고작 차로 10분 거리라고 한다.

예제2

예제 1
입력
```
2 5 20
5 10 2
10 15 2
```
예상 출력
```
7
```
예제 2
입력
```
2 5 20
5 10 2
7 15 1
```
예상 출력
```
10.4
```