ztarlitz

Господи, баянистая же задачка по алгоритмическому программированию.
Разбили точки на две половины с одинаковым количеством точек вертикальной прямой. Рекурсивно нашли ответ для двух половин — пусть такой минимальный периметр по двум половинам равен P.
Осталось разобрать треугольники, у которых одна вершина в одной половине, а две других — во второй. Нам достаточно рассматривать только точки на расстоянии <= P / 2 от прямой деления.
Теперь идём по точкам в этой полосе сверху вниз, поддерживая набор точек, которые находятся по вертикали от нашей на расстоянии не более P / 2. Т. е. идём эдаким плывущим окошком ширины P / 2 — получаются два вида событий — точка попала внутрь окна и точка вышла из окна.
Если внутри окна не существует треугольника, который периметром меньше P, то в этом окне (навскидку) никак не может быть больше 7 точек (раз окно — прямоугольник P x P / 2). Эти 7 точек можно уже за кубическую сложность перебрать. Иначе там обязательно есть треугольник периметром меньше P, на который мы наткнёмся. Каждый раз, натыкаясь на такой треугольник будем попросту уменьшать P до нового значения.

Тем самым, получился алгоритм со сложностью, удовлетворяющей оценке T(n) = 2T(n / 2) + O(nlogn), решением которой является O(n*log^2(n))

Можно вместо полного перебора использовать какой-то жадный алгоритм, всегда пытается найти треугольник минимального периметра. Тут есть такой профит, что имея уже некий треугольник, можно игнорировать все расстояния которые не меньше, чем половина его периметра. С оценкой такого алгоритма затрудняюсь.

Можно посчитать все расстояния (N² и ассоциировать эти расстояния с обеими точками (2N памяти), можно с сортировкой по возрастанию.

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

Можно попробовать соптимизировать, при ассоциации с точками ближайших расстояний хранить только минимальные ну скажем 3. Тут надо проанализировать, как бы не потерять истинное решение в результате такой оптимизации.