EduBrick

Наибольший треугольник

1700 мс · 256 МБ · всё или ничего

Из данных точек выберите три так, чтобы площадь треугольника была наибольшей. Выведите удвоенную площадь - она целая.

Формат ввода

В первой строке - число точек nn (1≤n≤50001 \le n \le 5000).

В следующих nn строках - координаты точек, целые, по модулю не превосходящие 10610^6. Точки могут повторяться.

Формат вывода

Выведите наибольшую удвоенную площадь треугольника с вершинами в данных точках - целое число.

Примеры

ввод
4
0 0
4 0
4 4
0 4
вывод
16
ввод
3
0 0
1 1
2 2
вывод
0
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.