Задача Трещины (CRACKS)

В поисках сокровища грабители наткнулись на препятствие в виде прямоугольной каменной плиты, закрывающей вход в подземелье. Плита усеяна трещинами.  Каждая трещина представляет собой прямолинейный отрезок. Никакие две трещины не пересекаются и не касаются друг друга. Никакая трещина не касается границ плиты. Чтобы попасть в подземелье, нужно разломить плиту. Разлом представляет собой ломаную линию, соединяющую противоположные стороны плиты. Разлом может включать в себя существующие трещины или части трещин.Пробивание разлома в плите  – это долгий и утомительный процесс, однако те части разлома, которые проходят по существующим трещинам, пробивать не надо. Грабители, с помощью хакера Васи, нашли такой оптимальный разлом, для которого суммарная длина пробиваемой части разлома минимальна.

Определите длину пробиваемой части оптимального разлома.

Технические условия:

Напишите программу CRACKS, которая читает входные с клавиатуры и записывает ответ в на экран. В первой строке  ввода находятся два действительных числа W, H  – ширина и высота плиты. В выбранной системе координат, плита представляет собой прямоугольник с вершинами в точках    (0,0) (W,0),(W,H)  и  (0,H) Во второй строке находится число N  – количество трещин. В следующих N строках находятся по 4 числа X₁^k, Y₁^k, X₂^k,Y₂^k      – координаты концов трещин    (k=0, 1...N)  .

Ответ должен содержать единственное число – суммарную длину пробиваемой части оптимального разлома. Ответ не должен отличаться от правильного больше, чем на   10^-3  .

Ограничения:

0.0<W<10000.0  0.0<H<=1000.0   1<=N<=100

Пример: