Ева изучает геометрию. Текущая тема о выпуклых многоугольниках, но Ева предпочитает прямоугольники. Рабочая тетрадь Евы содержит рисунки нескольких выпуклых многоугольников, и ей интересно, какова площадь максимального прямоугольника, который помещается внутри каждого из них.
Помоги Еве! Для заданного выпуклого многоугольника найдите прямоугольник максимально возможной площади, вписанный в этот многоугольник. Стороны прямоугольника должны быть параллельны координатным осям.
Первая строка содержит количество сторон многоугольника n (3 ≤ n ≤ 100 000). Следующие n строк содержат вершины многоугольника - два целых числа x[i]
и y[i]
(-10^9
≤ x[i]
, y[i]
≤ 10^9
) в строке. Вершины перечислены в порядке обхода по часовой стрелке. Многоугольник является выпуклым.
Выведите четыре действительных числа x[min]
, y[min]
, x[max]
and y[max]
- координаты двух вершин прямоугольника (x[min]
< x[max]
, y[min]
< y[max]
). Прямоугольник должен быть вписанным в многоугольник и иметь максимально возможную площадь.
Абсолютная точность координат должна быть не менее 10^(-5)
.
Абсолютная или относительная точность площади прямоугольника должна быть не менее 10^(-5)
То есть если A' фактическая максимально возможная площадь, то имеет место неравенство: min(|A − A'|, |A - A'| / A') ≤ 10^(-5)
.