Геометрическая задача на С++, Нахождение треугольника минимальной площади Опции

[Rudolf]

Задача такая: Из заданного на плоскости множества точек выбрать 3, не лежащих на одной прямой и состовляющих треугольник наименьшей площади.
Как я понимаю плоскость задаем в виде двумерного массива?А что с этим массивом потом делать?

[Michael_Rybak]

Плоскость нет (по-моему) смысла задавать двумерным массивом. Задавать нужно *точки*, а не плоскость. Точки можно задать (одномерным) массивом, каждый элемент - пара (x, y). Или двумя массивами - x[1..n] и y[1..n].

Лобовое решение - тремя вложенными циклами перебрать первую, вторую и третью точки, и выбрать наилучший треугольник. Это будет O(n^3).

Решение похитрее - за O(n^2). Расскажу, если кому-то действительно интересно.

Может можно и за O(n log n). Но это уже совсем сложно, надо думать.