EduBrick

Самый большой треугольник

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

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

Формат ввода

В первой строке — число nn (3≤n≤20003 \le n \le 2000). В следующих nn строках — целые координаты (∣x∣,∣y∣≤106|x|, |y| \le 10^6).

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

Выведите удвоенную площадь наибольшего треугольника.

Примеры

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