Задача №112795. Озера
Mr. Fox собирается посетить Шотландию, чтобы увидеть много красивых озер. Он слышал, что скимбоардинг(что-то вроде серфинга) это весело! И он хочет попробовать это, пока он тут.
Скоро он окажется на пляже со стороны озера. Пляж может быть представлен как бесконечное двумерное поле c N прямоугольными бассейнами с небольшим количеством воды в них. (Стороны бассейна паралельны осям координат). i -й бассейн описывается парой точек, двумя противоположными углами прямоугольника ( x 1, y 1) и ( x 2, y 2) . Прямоугольники могут произволно пересекаться друг с другом, в результате вода будет везде в объединении бассейнов. (включая границу бассейнов) Нигде более воды не будет. (Mr. Fox еще не настолько смелый, чтобы рисковать жизнью в озере)
Mr. Fox стартует и затем движется сквозь воду в каком-то направлении по прямой линии, пока он не упрется в точку где нет воды. Другими словами его дебют в скимбординге состоит из отрезка, который полностью лежит в объединении бассейнов с водой. Какую максимальную длину отрезка он может проехать?
В первой строке написано число N , количество бассейнов. Далее следуют N строк. В i -ой строке находятся 4 числа x 1, y 1, x 2, y 2 разделенных пробелом.
1 ≤ N ≤ 20
1 000 000 ≤ x 1 < x 2 ≤ 1 000 000
1 000 000 ≤ y 1 < y 2 ≤ 1 000 000
Выведите единственное число длину наибольшего возможного пути с точностью 6 знаков после запятой.
Абсолютная погрешность свыше 10 - 6 будет проигнорирована.
1 0 0 3 4
5.0000000000
2 2 0 4 3 3 2 5 5
5.8309518948