언덕길 주행

시간 제한1초메모리 제한128 MB

요약
도로마다 속도에 따른 연료 소비 모델과 최고 속도 제한이 있을 때, 주어진 연료로 집에 가는 최소 시간을 구합니다.
난이도

어려움10점 중 8점

유형
이분 탐색, 그리디, 수학
정답자
아직 제출이 없습니다

문제

상근이는 근처 산에 차를 타고 올라왔고, 이제 최대한 빨리 집으로 돌아가려고 한다. 차에 남은 기름이 얼마 없기 때문에 최대한 효율적으로 운전해야 한다.

집으로 가는 길의 일부는 오르막이고 일부는 내리막이다. 각 도로 구간은 저마다 다른 길이와 경사를 가진다. 차에 남은 기름의 양이 주어질 때, 집에 도착하는 데 걸리는 최소 시간을 구하시오.

차의 연료 소비는 간단하게 모델링된다. 단위 거리당 연료 소비량 cc (리터/km)는 속도 vv에 비례하며, 도로의 경사 ss에 의해 값이 조정된다.

c=max⁡(0, αv+βs)c = \max(0,\ \alpha v + \beta s)

여기서 α\alpha는 평지에서의 연료 소비 계수, vv는 속도(km/h), ss는 도로의 경사, β\beta는 양의 상수이다. 예를 들어 어떤 언덕을 연료 없이 1010 km/h로 내려갈 수 있다면, 같은 언덕을 올라갈 때 드는 연료는 평지에서 1010 km/h 더 빠르게 달릴 때와 같다. 가속과 감속은 연료를 쓰지 않고 즉시 이루어진다. 또한 차에는 최고 속도 vmaxv_{max}가 있어 이를 넘을 수 없다.

거리는 미터 단위로 주어진다. 수평 길이가 xx이고 높이 변화가 yy인 도로 구간에서 실제 주행 거리는 x2+y2\sqrt{x^2 + y^2} 미터이고, 그 경사는 s=y/xs = y / x이다. 속도는 km/h, 이동 시간은 시간(hour) 단위로 측정한다.

입력

첫째 줄에 테스트 케이스의 개수 TT (1≤T≤1001 \le T \le 100)가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다.

각 테스트 케이스의 첫째 줄에는 네 실수 α\alpha (0.5≤α≤1000.5 \le \alpha \le 100), β\beta (0.1≤β≤1000.1 \le \beta \le 100), vmaxv_{max} (10≤vmax≤20010 \le v_{max} \le 200), ff (0≤f≤500 \le f \le 50)가 주어진다. vmaxv_{max}는 차의 최고 속도(km/h), ff는 남은 기름의 양(리터)이다.

다음 줄에는 도로의 개수 rr (1≤r≤100001 \le r \le 10000)이 주어진다.

이어지는 rr개의 줄에는 각각 두 실수 xix_i와 yiy_i (1≤xi≤10001 \le x_i \le 1000, −1000≤yi≤1000-1000 \le y_i \le 1000)가 주어지며, 이는 ii번째 도로의 수평 길이와 높이 변화(미터)이다. 각 도로의 경사는 일정하다.

출력

각 테스트 케이스마다 집으로 돌아오는 최소 시간(시간 단위)을 소수점 아래 정확히 6자리로 반올림하여 한 줄에 출력한다 (예: printf("%.6f")). 남은 기름으로 집에 돌아올 수 없으면 대신 IMPOSSIBLE을 출력한다. 집에 돌아올 수 있는 경우 걸리는 시간은 항상 24시간 미만이다. 테스트 데이터는 정답이 반올림 경계에 가깝지 않도록 구성되어 있다.

예제4

  1. 예제 1

    입력
    3
    10.0 1.0 150 0.0
    1
    100.0 -100.0
    10.0 100.0 150 1.0
    2
    100 0
    100 100
    0.5 0.1 100 10
    3
    1000 0
    100 10
    100 -10
    
    예상 출력
    1.414214
    IMPOSSIBLE
    0.072120
    
  2. 예제 2

    입력
    1
    2.0 1.0 120 30
    1
    800 0
    
    예상 출력
    0.042667
    
  3. 예제 3

    입력
    1
    5.0 20.0 100 2.0
    1
    300 250
    
    예상 출력
    IMPOSSIBLE
    
  4. 예제 4

    입력
    2
    1.5 2.0 100 18
    2
    900 10
    200 -30
    6.0 0.5 160 40
    2
    1000 0
    150 120
    
    예상 출력
    0.101026
    0.213573