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

sbj>Есть кривая (массив точек).
sbj>Необходимо определить координаты минимального по площади прямоугольника описывающего
sbj>данную кривую и гол наклона этого прямоугольника относительно оси координат.

Строим выпуклую оболочку этой кривой.
Поскольку она задана набором точек (скажем, N штук), то оболочка — это многоугольник (скажем, K-сторонний).
Находим описывающие прямоугольники, соосные поочерёдно каждой стороне оболочки. Среди них — ищем минимальный по площади.

O(N*log(N)) на построение оболочки.
O(K^2) для тупого перебора прямоугольников (для каждого за линейное время находим минимумы-максимумы координат вершин оболочки в повёрнутой системе координат). А если запоминать крайние вершины — то O(K).