Как найти треугольник с максимальным периметром среди большого набора точек

Что проверяют

Сможете ли вы уйти от очевидного перебора за O(n³), когда точек сотни тысяч, и обосновать, почему оптимизация корректна. Следом обычно спрашивают про худший случай и про вырожденные тройки точек на одной прямой.

Как отвечать

Сначала уточните условие. Если даны не точки, а длины отрезков, это другая задача: сортируете по убыванию и берёте первую тройку, где a[i] < a[i+1] + a[i+2], итого O(n log n).

Для точек на плоскости:

• перебор: три вложенных цикла, O(n³). Для тысячи точек это около 1,7·10⁸ троек, для миллиона нереально;
• ключевое наблюдение: вершины искомого треугольника можно искать только на выпуклой оболочке. Если зафиксировать две вершины, периметр как функция третьей точки выпуклый, а максимум выпуклой функции на многоугольнике достигается в его вершине;
• выпуклая оболочка: алгоритм Эндрю (monotone chain) или Грэхема за O(n log n);
• перебор по оболочке: O(h³), где h число вершин оболочки. Для случайных точек в квадрате h растёт примерно как логарифм от n, поэтому на практике это быстро.

Честно назовите худший случай: если все точки лежат на окружности, оболочка содержит все n точек и выигрыша нет. Лучше сказать об этом самому.

Детали реализации на Java: координаты храните в long, например record Point(long x, long y), иначе квадрат разности и векторное произведение в int переполнятся. Векторное произведение при построении оболочки считайте в целых числах, без double, чтобы не ошибиться на почти коллинеарных точках. Расстояние считайте через Math.sqrt от суммы квадратов или через Math.hypot, который медленнее, зато не переполняется.

Где спотыкаются

Сразу пишут тройной цикл и не обсуждают ограничения. На «большом наборе» интервьюер ждёт хотя бы идеи с оболочкой.

Не исключают вырожденные тройки: три точки на одной прямой дают ненулевой «периметр», но треугольником не являются. Проверка простая: векторное произведение равно нулю.

Путают задачу с максимальной площадью, где тоже работает оболочка, но для перебора по ней есть отдельные быстрые приёмы. Переносить их на периметр без доказательства рискованно.