Прошлой ночью я видел, как ты бежишь
По бескрайним полям благодати
Ты больше не был сломлен и не испытывал боли.[^1]
Вы нашли бескрайнее поле и забыли на нём о прошлом, полном страданий и боли. Вы бежите, словно ребёнок, среди даров Божьей благодати.
Однако обнаружилась проблема: на этом поле есть несколько ущелий, и вы в любой момент рискуете в них упасть. Чтобы продолжить беззаботный бег, вы решили окружить ущелья оградами.
Шириной ущелий можно пренебречь и считать каждое из них отрезком. Эти отрезки могут пересекаться, а ограда должна состоять из одной или нескольких замкнутых кривых без самопересечений, попарно не пересекающихся, так, чтобы каждое ущелье целиком лежало в замкнутой области, ограниченной одной из этих кривых.
Разумеется, ограды требуют ресурсов, причём расход ресурсов пропорционален длине ограды. Вы хотите минимизировать общий расход, поэтому нужно найти точную нижнюю грань суммарной длины оград. Иными словами, требуется найти наибольшее действительное число $x$, для которого не существует способа построить ограды с суммарной длиной меньше $x$.
Входные данные
Данные считываются из файла fields.in.
Первая строка входного файла содержит целое число $n$ — количество ущелий.
Следующие $n$ строк описывают ущелья. Строка $i$ содержит четыре целых числа $a_i,b_i,c_i,d_i$: ущелье $i$ является отрезком, соединяющим точки $(a_i,b_i)$ и $(c_i,d_i)$. Гарантируется, что концы одного отрезка не совпадают, а разные отрезки не имеют общих концов. Никакие три точки не лежат на одной прямой.
Выходные данные
Выведите ответ в файл fields.out.
Выведите в одной строке одно действительное число — точную нижнюю грань суммарной длины оград. Минимум из абсолютной и относительной погрешностей вашего ответа по отношению к эталонному не должен превышать $10^{-6}$.
Примеры
Входные данные 1
1 0 0 0 1
Выходные данные 1
2.00000000
Примечание
Прямоугольник с вершинами $(-0.01,-0.01),(-0.01,1.01),(0.01,1.01),(0.01,-0.01)$ полностью содержит входной отрезок и имеет периметр $2.08$, немного больший точной нижней грани.
Можно доказать, что способа с длиной ровно $2$ не существует. Бесконечно «стягивая» квадрат к входному отрезку, можно получить способ с любой длиной, большей $2$.
Входные данные 2
4 -1 7 0 7 0 0 0 1 2 -3 5 5 2 2 6 -1
Выходные данные 2
23.563573998194637061425470524757
Примечание
На рисунке показаны входные отрезки. Обратите внимание, что отрезки могут пересекаться:
Рисунок 1: пояснение к примеру 2
Бесконечно «приближаясь» к этим красным кривым, можно получить способ с любой суммарной длиной, большей ответа. Из примера 1 легко понять, что красный отрезок в левом верхнем углу учитывается дважды.
Входные данные 3
4 -1 1 -1 3 0 4 2 4 3 1 3 3 0 0 2 0
Выходные данные 3
13.656854249492380195206754896839
Примечание
Ответ равен $8+4\sqrt{2}$.
Пояснение показано на рисунке:
Рисунок 2: пояснение к примеру 3
Бесконечно «приближаясь» к этим красным кривым, можно получить способ с любой суммарной длиной, большей $8+4\sqrt{2}$.
Примеры 4
См. файлы fields/fields4.in и fields/fields4.ans в каталоге участника.
Ограничения
Для 5% данных гарантируется $1\le n\le1$.
Для 10% данных гарантируется $1\le n\le2$.
Для 15% данных гарантируется $1\le n\le10$.
Для 30% данных гарантируется $1\le n\le15$.
Для 45% данных гарантируется $1\le n\le30$.
Для 55% данных гарантируется $1\le n\le60$.
Для 65% данных гарантируется $1\le n\le120$.
Для 75% данных гарантируется $1\le n\le200$.
Для ещё 10% данных гарантируется, что ответ содержит не более двух кривых.
Для 100% данных гарантируется $1\le n\le250$, $0\le|a_i|,|b_i|,|c_i|,|d_i|\le10^9$. Концы одного отрезка не совпадают, а разные отрезки не имеют общих концов. Никакие три точки не лежат на одной прямой.
[^1]: Строки песни в условии взяты из Open Fields of Grace в исполнении Jackie Evancho; композиторы — Lisa Venkatrathnam и Paul Sumares.