Задача Трещины (CRACKS)
В поисках сокровища грабители наткнулись на препятствие в виде прямоугольной каменной плиты, закрывающей вход в подземелье. Плита усеяна трещинами. Каждая трещина представляет собой прямолинейный отрезок. Никакие две трещины не пересекаются и не касаются друг друга. Никакая трещина не касается границ плиты. Чтобы попасть в подземелье, нужно разломить плиту. Разлом представляет собой ломаную линию, соединяющую противоположные стороны плиты. Разлом может включать в себя существующие трещины или части трещин.Пробивание разлома в плите – это долгий и утомительный процесс, однако те части разлома, которые проходят по существующим трещинам, пробивать не надо. Грабители, с помощью хакера Васи, нашли такой оптимальный разлом, для которого суммарная длина пробиваемой части разлома минимальна.
Определите длину пробиваемой части оптимального разлома.
Технические условия:
Напишите программу CRACKS, которая читает входные с клавиатуры и записывает ответ в на экран. В первой строке ввода находятся два действительных числа W, H – ширина и высота плиты. В выбранной системе координат, плита представляет собой прямоугольник с вершинами в точках (0,0) (W,0),(W,H) и (0,H) Во второй строке находится число N – количество трещин. В следующих N строках находятся по 4 числа X1k, Y1k, X2k,Y2k – координаты концов трещин (k=0, 1...N) .
Ответ должен содержать единственное число – суммарную длину пробиваемой части оптимального разлома. Ответ не должен отличаться от правильного больше, чем на 10-3 .
Ограничения:
0.0<W<10000.0 0.0<H<=1000.0 1<=N<=100
Пример:
|
Ввод 8.0 7.0 4 1.0 2.0 2.0 5.0 2.0 3.0 5.0 2.0 6.0 2.0 6.0 4.5 7.0 4.0 7.9 3.0 |
Вывод 3.73245553203
|