Здравствуйте, DK3981, Вы писали:

T>>Из-за утверждения 2 можно перебрать все пары точек, которые будут задавать ориентацию. Полученная сложность O(N^3). Устраивает? В принципе, сложность можно уменьшить.
DK>O(N^2):
DK>Сперва стоим выпуклую оболочку, а потом для каждой из её сторон (N) ищем параметры прямоугольника (за N перебираем все точки, проектируя на прямую + считая расстояние до прямой).
Верно, это было заложено под "можно уменьшить". На самом деле можно еще сильнее уменьшить