|
Гонки на лодках
(Время: 1 сек. Память: 16 Мб Сложность: 64%)
Петя собирается участвовать в соревнованиях гоночных лодок. Гонка будет происходить в длинном узком канале. Канал проложен с запада на восток, берега канала имеют вид ломаной.
Введем систему координат таким образом, чтобы западный конец канала имел x-координату равную 0, а восточный конец канала – x-координату равную l. Ломаная, описывающая южный берег канала, имеет вершины в точках (x0, y0), (x1, y1), ... , (xn, yn), где 0 = x0 < x1 < ... < xn = l. Северный берег канала имеет аналогичную форму, но находится на w к северу, таким образом он описывается ломаной с координатами вершин (x0, y0+w), (x1, y1+w), ... , (xn, yn+w).
Лодка Пети может начать гонку в любой точке на стартовой прямой (отрезок (0, y0) −(0, y0+w)) и закончить гонку в любой точке финишной прямой (отрезок (l, yn) − (l, yn+w)). Лодка настолько мала, что можно считать ее точкой. Когда лодка перемещается, она может проходить сколь угодно близко к берегам канала.
Чтобы увеличить свои шансы на победу, Петя хочет, чтобы кратчайший путь от стартовой до финишной позиции был как можно меньше. Помогите ему выяснить длину этого пути.
Входные данные
Первая строка входного файла INPUT.TXT содержит n (1 ≤ n ≤ 100). Следующие n+1 строк содержат пары целых чисел (xi, yi), которые описывают южный берег канала (0 = x0 < x1 < ... < xn ≤ 104, |yi| ≤ 104). Последняя строка входного файла содержит целое число w (1 ≤ w ≤ 104).
Выходные данные
В выходной файл OUTPUT.TXT выведите одно вещественное число – длину кратчайшего пути через канал от стартовой прямой до финишной. Ответ должен отличаться от правильного не более чем на 10-6.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3
0 0
2 2
3 -1
5 0
2 | 5.41421356237309505 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
