00B-1. Как побольше захватить?

Имя входного файла:	area.in
Имя выходного файла:	area.out
Ограничение по времени:	1 s
Ограничение по памяти:	256 megabytes

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

Формат входного файла

В первой строке входного файла содержится одно число N – число столбов в поле 1 ≤ N ≤ 100000. Далее следуют N строчек, в i-ой из которых координаты i-ого столба x_i, y_i. -10⁴ ≤ x_i, y_i ≤ 10⁴

Формат выходного файла

В единственной строке выходного файла выведите ответ с точностью не менее 6 знаков после запятой.

Пример:

area.in	area.out
8 0 0 0 4 4 0 1 1 1 2 2 1 2 2 4 4	15.000000

Источник: Чемпионат ПетрГУ по программированию. 1 марта 2015 года

Обсудить       Отправить решение



Версия для печати