물탱크

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

요약
매일 반복되는 물 사용 일정이 주어질 때, 탱크가 바닥나지 않게 하는 최소 펌프 속도를 구한다.
난이도

어려움10점 중 8점

유형
이분 탐색, 시뮬레이션, 누적 합, 그리디
정답자
아직 제출이 없습니다

문제

아파트를 지으면서 주민이 쓸 물을 담아 두는 용량 LL짜리 물탱크를 설치했다. 이 탱크는 수도 회사와 주민 사이에서 완충 장치가 된다.

물을 쓰는 동안 물이 모자라면 안 된다. 탱크에는 펌프로 물을 채운다. 펌프가 강할수록 물이 모자랄 걱정은 줄지만, 강한 펌프는 비싸다. 그래서 조건을 만족하는 가장 약한 펌프의 성능을 알아야 한다.

하루 물 사용 일정표는 매일 똑같다. 일정표는 여러 개의 일정으로 이루어지고, 각 일정은 사용 시작 시각, 사용 종료 시각, 그 구간에서 단위 시간당 쓰는 물의 양으로 정해진다.

일정표를 보고 펌프가 물을 넣어야 하는 최소 속도를 구하는 프로그램을 작성하라.

다음 조건이 성립한다.

  • 하루는 86400단위 시간이다.
  • 시각 0보다 먼저 시작하는 일정은 없고, 시각 86400보다 늦게 끝나는 일정도 없다.
  • 두 일정은 서로 겹치지 않는다.
  • 일정이 없는 동안에는 물을 쓰지 않는다.
  • 펌프는 하루 종일 멈추지 않고 일정한 속도 rr로 물을 넣는다. rr는 음이 아닌 실수다.
  • 저장된 물의 양이 용량 LL을 넘으면 넘친 만큼은 흘러 나가므로, 저장량은 항상 LL 이하다.
  • 탱크는 첫째 날 시각 0에 가득 차 있다.

시각 tt의 저장량을 V(t)V(t)라고 하면 모든 시각에서 V(t)≥0V(t) \ge 0이어야 한다. 일정표는 매일 같은 형태로 끝없이 반복되고, 이 조건은 모든 날에 대해 성립해야 한다. 이를 만족하는 가장 작은 rr를 구하라.

입력

입력은 여러 개의 데이터 집합으로 이루어진다. 각 데이터 집합은 일정표 하나를 나타내며, 형식은 다음과 같다.

N L
s1 t1 u1
...
sN tN uN

첫 줄에는 정수 NN과 LL이 주어진다 (1≤N≤864001 \le N \le 86400, 1≤L≤1061 \le L \le 10^6). NN은 일정의 개수이고 LL은 탱크의 용량이다.

이어지는 NN개의 줄 중 ii번째 줄에는 ii번 일정을 나타내는 세 정수 sis_i, tit_i, uiu_i가 주어진다. sis_i와 tit_i는 사용 시작 시각과 종료 시각이고, uiu_i는 그 구간에서 단위 시간당 쓰는 물의 양이다 (1≤ui≤1061 \le u_i \le 10^6). 시각은 0≤s1<t1≤s2<t2≤⋯≤sN<tN≤864000 \le s_1 < t_1 \le s_2 < t_2 \le \cdots \le s_N < t_N \le 86400을 만족한다.

입력의 끝에는 0이 두 개 있는 줄이 오고, 이 줄은 처리하지 않는다.

한 입력에 들어 있는 데이터 집합은 20개 이하이고, 모든 데이터 집합의 NN을 더한 값은 100000 이하다.

출력

각 데이터 집합마다 펌프가 넣어야 하는 단위 시간당 최소 물의 양을 소수점 아래 여섯째 자리까지 반올림해 한 줄에 출력한다. 소수점 아래 자릿수는 정확히 여섯 자리여야 한다.

정답은 항상 10610^6 이하다. 정답이 소수점 아래 여섯째 자리 반올림의 경계값에서 10−910^{-9} 이내로 가까운 경우는 없으므로, 출력할 값은 하나로 정해진다.

예제1

  1. 예제 1

    입력
    1 100
    0 86400 1
    1 100
    43200 86400 1
    0 0
    
    예상 출력
    1.000000
    0.997685