Задача C. Ударим мостом по бездорожью

Автор:Жюри ROI-2007   Ограничение времени:1 сек
Входной файл:bridge.in   Ограничение памяти:256 Мб
Выходной файл:bridge.out  
Максимальный балл:100  

Условие

Профиль Уральских гор задается ломаной (x1, y1), (x2, y2), …, (xN, yN), для координат вершин которой верны неравенства x1 < x2 < … < xN. Начальные и конечные точки профиля расположены на уровне моря (y1 = yN = 0).

На горном профиле заданы две различные точки A и B, между которыми требуется проложить дорогу. Эта дорога будет проходить по склонам гор и проектируемому горизонтальному мосту, длина которого не должна превышать L. Оба конца моста находятся на горном профиле. Дорога заходит на мост с одного конца и выходит с другого. Мост не может содержать точек, расположенных строго под ломаной (строительство тоннелей не предполагается).

Достоверно известно, что строительство такого моста в данной местности возможно, причем позволит сократить длину дороги из точки A в точку B. Требуется написать программу, которая определит такое расположение горизонтального моста, что длина дороги от точки A до точки B будет наименьшей.

Решения, корректно работающие при N ≤ 2000, будут оцениваться, исходя из 80 баллов.

Формат входного файла

Первая строка входного файла содержит два целых числа N и L — количество вершин ломаной (2 ≤ N ≤ 105) и максимальную длину моста (1 ≤ L ≤ 106) соответственно. Вторая строка входного файла содержит координаты точки A, третья строка — координаты точки B. Точки A и B различны.

Последующие N строк содержат координаты вершин ломаной (x1, y1), (x2, y2), …, (xN, yN). Координаты вершин ломаной, а также точек A и B, задаются парой целых чисел, не превосходящих по абсолютному значению 106. Гарантируется, что x1 < x2 < … < xN и y1 = yN = 0, а также, что точки A и B принадлежат ломаной.

Формат выходного файла

В первой и второй строках выходного файла выведите координаты концов моста с точностью не менее 5 знаков после десятичной точки. В случае, когда решений несколько, выведите любое из них.

Примеры тестов

Входной файл (bridge.in) Выходной файл (bridge.out)
1
4 6
13 0
2 1
1 0
5 4
11 -2
13 0
13.00000 0.00000
9.00000 0.00000
2
6 8
3 -6
11 -2
0 0
4 -8
6 -4
7 -4
9 -6
12 0
2.00000 -4.00000
10.00000 -4.00000

0.045s 0.008s 17