Задача . C. Оптимальный периметр многоугольника

Есть \(n\) точек на плоскости. Многоугольник, сформированный этими \(n\) точками, строго выпуклый, то есть многоугольник выпуклый и нет трех коллинеарных точек (то есть лежащих на одной прямой). Точки пронумерованы от \(1\) до \(n\) по часовой стрелке.

Определим расстояние между двумя точками \(p_1 = (x_1, y_1)\) и \(p_2 = (x_2, y_2)\) как их манхэттенское расстояние: \(\)d(p_1, p_2) = |x_1 - x_2| + |y_1 - y_2|.\(\)

Более того, определим периметр многоугольника как сумму манхэттенских расстояний между всеми соседними парами точек на нем; если точки на многоугольнике упорядочены как \(p_1, p_2, \ldots, p_k\) \((k \geq 3)\), тогда периметр многоугольника равен \(d(p_1, p_2) + d(p_2, p_3) + \ldots + d(p_k, p_1)\).

Для некоторого параметра \(k\) рассмотрим все многоугольники, которые могут быть сформированы из любых \(k\) точек заданного многоугольникв и не самопересекаются. Для каждого такого многоугольника рассмотрим его периметр. Определим \(f(k)\) как максимальный периметр среди всех таких многоугольников.

Обратите внимание, что при проверке многоугольника на самопересечение, ребра многоугольника рисуются как прямые линии. Например, на следующих рисунках:

В многоугольнике, который изображен посередине, последовательность точек (\(p_1, p_3, p_2, p_4\)) неправильная потому, что многоугольник самопересекается. Правый многоугольник (ребра которого напоминают Манхэттенское расстояние) имеет такую же последовательность и не самопересекается, но мы рассматриваем ребра как прямые отрезки. Правильный способ нарисовать этот многоугольник — это использовать последовательность (\(p_1, p_2, p_3, p_4\)), пример которого можно увидеть на левом рисунке.

Вычислите \(f(3), f(4), \ldots, f(n)\). Другими словами, найдите максимально возможный периметр для каждого количества точек (то есть от \(3\) до \(n\)).