Точки в россыпи? Никакой четкой системы нет?
Тогда можно так:
Берешь одну точку. Потом для каждой из оставшихся строишь прямую по базовой точке и второй. Потом строишь из первой точки перепендикуляр и проверяешь есть ли хоть одна точка которая лежит на этом перпиндикуляре? Если нету - значит прямоугольник на основе первых двух точек построить вообще нельзя. Если есть хоть одна, строишь перпендикуляр к первой прямой из второй точки. Опять проверяешь есть ли точки лежащие на нем? Если есть сравниваешь четветрую найденую точку с третьей во первых по расстоянию до первой и второй точки (должно совпадать), во вторых расстояние между третей и четвертой должно совпадать с расстоянием между первой и второй. Можно в принципе проверять не расстояния а вектора, но расстояния по моему проще :)
Таким образом накапливаешь список прямоугольников которые вообще возможно построить на данной россыпи точек. Потом сравниваешь их периметры.

Ну это вообще-то не "другя формулировка" а "изначально другой подход" :)

А расстояния в моем подходе можно и не считать. Там можно расценивать все найденые отрезки как вектора и делать простое сравнение "если X1=X2 и Y1=Y2 то найденые отрезки могут быть противоположными сторонами прямоугольника". И даже без перемножения векторов :)

Можно конечно и четырехугольники считать, но тогда задача усложнится на порядок :)
Берем три точки, проводим по ним два отрезка AB и BC. Теперь ищем такую четвертую точку D чтобы отрезок CD не пересекал AB и не совпадал с BC, а потом еще проверяем чтобы отрезок DA не пересекал BC. Иначе вместо четырехуголника у нас получится шестиугольник :)
Плюс везде проверки на совпадение двух точек...
Не, можно конечно и четырехуголники искать, но прямоугольники проще :)

Alex Friendя накодил как советовал товарищ Lelikk, парочка шаманств и она работает, только не совсем правильно находит косые прямоугольники, то есть те, у которых стороны не параллельны осям координат.
Если не находит - значит ошибся в кодировании формул перемножения векторов.
Метод должен работать, хотя на мой взгляд он и не является самым оптимальным. Уравнение перпендикулярных прямых проще чем векторная алгебра :)

Alex FriendЯ вам новую задачу принес на похожую тему.
Дано множетсво случайно разбросанных точек и такое же множетсво окружностей. Надо провести прямую, пересекающую максимальное количество окружностей.
Есть идеи, не могу сформулировать внятно, что предложите?
Прямые по данным точкам проводить?
Ну можно, по двум точкам провести прямую, взять от нее перпендикуляр, совместить перпендикуляр с центром очередной окружности и найти точку пересечения между исходной прямой и полученой. Потом считаешь расстояние от центра окружности до найденой точки - это минимальное расстояние между центром окружности и исходной прямой. Если оно меньше радиуса окружности, значит прямая ее пересекает. И по циклу, для каждой прямой проверяешь все окружности....
Это если в лоб решать :) А иначе думать надо.