영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
(그림은 원문 저장소에서 볼 수 있습니다)
Figure 1: The shape of the mountain in samples 1 and 2. The red segments are too steep to walk on. The dashed blue lines are bridges that the hikers build.
A mountain range consists of n points, (x_1, y_1) to (x_n, y_n), where x_1 < x_2 < … < x_n. Between point i and point i+1 there is a line segment.
Some hikers want to cross the entire mountain range, that is, walk from point 1 to point n. However, they cannot walk on a line segment if its slope is strictly greater than d. Here we define the slope of the line through (x_i, y_i) and (x_j, y_j) as
(|y_i - y_j|)/(|x_i - x_j|)
where |x| denotes the absolute value of x.
To make the hike possible, they can build bridges in the mountain range. A bridge is also represented as a line segment, and is always built between two points i and j. A bridge may of course not have a slope greater than d, and furthermore it is not possible to build a bridge that passes through the mountain at any place.
Determine the minimum total length of the bridges that need to be built in order to make the hike possible.
Input
The first line contains the integer n and the floating-point number d (2 ≤ n ≤ 1000, 0 < d ≤ 10^5). d is given with at most three decimals of precision.
The following n lines each contain two integers 0 ≤ x_i, y_i ≤ 10^6, the coordinates of point i, also separated by a space. It is guaranteed that x_i < x_{i+1}.
Output
Print a floating-point number: the minimum total length of bridges needed to make the hike possible. If it is impossible to complete the hike no matter how the bridges are built, print -1 instead.
Your answer will be accepted if the absolute error is less than 10^-3. It is guaranteed that the result for a test case is not affected by a small change of the number d (this is to avoid precision errors when comparing floating-point numbers).
Scoring
Your solution will be tested on a set of test groups. To earn points for a group, you must pass all test cases in that group.
| Group | Points | Constraints |
|---|---|---|
| 1 | 40 | n ≤ 100 |
| 2 | 60 | No additional constraints. |
예제
예제 1
10 1.2 0 0 2 2 3 0 4 1 5 0 6 1 7 0 8 0 9 2 11 0
5.06450
예제 2
11 1.6 0 0 2 3 4 3 5 5 6 1 7 7 8 3 9 5 12 2 13 3 15 1
9.23155
예제 3
3 1.9 0 0 10000 19999 30000 0
-1
예제 4
7 0.8 0 0 50000 20000 120000 90000 170000 70000 180000 40000 240000 40000 310000 0
226157.73106