eolymp
bolt
Try our new interface for solving problems
Məsələlər

Параллелограмм

Параллелограмм

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Решение многих задач компьютерной графики связано с обработкой гладких поверхностей, причем, как правило, известно лишь конечное число точек этой поверхности. В связи с этим возникает необходимость интерполяции рассматриваемой поверхности. Для удобства вычислений желательно, чтобы проекции узлов аппроксимации на некоторую плоскость располагались регулярно, например, совпадали с узлами двумерной решетки.

Один из способов сделать это заключается в том, чтобы заключить все проекции исходных точек в некоторый параллелограмм, стороны которого затем разбиваются на равные части, тем самым определяя решетку интерполяции. Так как общее число точек решетки при фиксированном шаге пропорционально площади параллелограмма, возникает необходимость в построении параллелограмма минимальной площади, содержащего все точки заданного набора.

Ваша задача немного проще. Вам не требуется найти сам параллелограмм, вычислите только его площадь.

Giriş verilənləri

В первой строке находится количество точек n (3n 5000) на плоскости. Далее n строк содержат по два целых числа – координаты точек в декартовой системе координат. Значения координат не превышают по модулю 500.

Гарантируется, что не все точки лежат на одной прямой.

Çıxış verilənləri

Вывести минимальную площадь параллелограмма, содержащего все заданные точки.

Nümunə

Giriş verilənləri #1
5
0 0
3 2
2 4
-1 2
2 1
Çıxış verilənləri #1
9.000
Mənbə ACM ICPC 2012-2013 NEERC Siberian Group