Господи, баянистая же задачка по алгоритмическому программированию.
Разбили точки на две половины с одинаковым количеством точек вертикальной прямой. Рекурсивно нашли ответ для двух половин — пусть такой минимальный периметр по двум половинам равен 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))
