루미 알고리즘

#1352플래티넘Mountain Hike

PO 2015 결선코딩출제 Emanuel Gedin영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

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.

GroupPointsConstraints
140n ≤ 100
260No 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

출처 표기

출처: Programmeringsolympiaden 2015년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.