В Квадратном Лесу завелись очень странные жуки. Они живут преимущественно под землей, но периодически выползают на поверхность. Всякий явлик, увидев такого жука, повинуется инстинктам и съедает его. Но эти жуки ядовитые и вызывают у явликов тяжелое отравление. Явлики не в силах контролировать свои инстинкты, поэтому единственный способ сохранить их здоровье – истребить всех жуков.
Долгое время все обитатели Квадратного Леса анализировали перемещение жуков по поверхности, которая, к слову, является абсолютно плоской. Оказалось, что жуки выбрали N дорожек на поверхности и движутся строго по ним. Дорожки представляют собой отрезки прямых, в концах которых находятся отверстия, ведущие под землю.
Для избавления от жуков было решено покрыть специальным раствором квадрат с центром в точке (0, 0) и сторонами, параллельными координатным осям, так, чтобы раствор попадал на каждую дорожку. Иными словами, соответствующие отрезки должны иметь хотя бы одну общую точку с квадратом. Используемый раствор очень токсичен и может навредить флоре Квадратного Леса, поэтому явлики хотят покрыть раствором как можно меньшую площадь.
Помогите обитателям леса вычислить, какую наименьшую площадь им необходимо покрыть раствором для уничтожения насекомых. Гарантируется, что искомый квадрат не вырожден в точку.
Центром квадрата считается точка пересечения его диагоналей
В первой строке входных данных находится число N – количество дорожек, которые используются жуками для перемещения. В последующих N строках содержится описание каждой дорожки в виде четырех целых чисел xi, yi, x'i, y'i, означающих, что i-я дорожка представлена отрезком с концами в точках (xi, yi) и (x'i, y'i). Гарантируется, что концы отрезка не совпадают. Числа в каждой строке разделены пробелами.
Ограничения на входные данные для получения 500 баллов (подзадача D1):
Ограничения на входные данные для получения 1500 баллов (подзадачи D1+D2):
Выведите одно вещественное число – наименьшую площадь квадрата, необходимую для уничтожения насекомых. Ответ будет считаться верным, если его абсолютная или относительная погрешность не превышает 10 - 4
2
-1 1 1 1
0 8 0 12
256.000000000
4
-1 -1 1 -1
1 -1 1 1
1 1 -1 1
-1 1 -1 -1
4.000000000
На рисунке изображены первый (слева) и второй (справа) тестовые примеры
