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

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

T>>Привет .
T>>Условие : Дан набор точек на плоскости (координаты х и у) необходимо построить прямоугольник наименьшей площади, который содержал бы в себе все эти точки. Прямоугольник может быть произвольо ориентированным (наклонным).
T>>Помогите придумать какое — нибудь дельное решение с нормальными затратами по времени.

T>Утверждение 1. Все стороны икомого прямоугольника будут на точках.
T>Утверждение 2. Найдется сторона, содержащая две точки.

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