Дети любят тортики
Дети любят тортики. Это очевидно. В этой задаче мы будем рассматривать только тортики, имеющие вид выпуклого многоугольника.
Каждый тортик следует разломать на куски. В этой задаче каждый кусок должен иметь вид невырожденного треугольника, вершины которого совпадают с вершинами исходного тортика. Куски не должны пересекаться, их объединение должно составлять весь исходный тортик.
Некоторые дети также любят справедливость. Назовем числом несправедливости торта максимально возможную разницу между площадями его наибольшего и наименьшего кусков.
Вам следует найти число несправедливости для заданного торта.
Входные данные
Первая строка содержит количество вершин n (4 ≤ n ≤ 5000) в тортике. Каждая из следующих n строк содержит два целых числа x[i], y[i] - координаты вершин (-10^8 ≤ x[i], y[i] ≤ 10^8).
Выходные данные
Первая строка должна содержать число несправедливости торта, выведенное в точности с одним десятичным знаком.
Следующие две строки должны описывать метод разбиения торта для получения указанного числа несправедливости. Первая строка должна содержать индексы вершин наибольшего куска. Вторая строка должна содержать индексы вершин наименьшего куска. Вершины нумеруются числами от 1 до n.