Имеется следующая задачка:
Даны 2 множества точек на плоскости. Выбрать три различные точки первого множества так, чтобы треугольник с вершинами в этих точках покрывал все точки второго множества и имел минимальную площадь.

Я себе ход решения представляю следующим образом:
1) Пусть первое множество состоит из n элементов. Нам нужно пересмотреть всевозможные комбинации с тремя точками из этого множества. Т.о. количество всевозможных вариантов - число сочетаний из n по 3.
2) Пусть выбраны некоторые три точки. У нас имеются их координаты. Строим треугольник по этим трем точкам.
3) Проверяем поочередно все точки на вхождение в область построенного треугольника.
4) Если все входят, то высчитываем площадь по формуле(например Герона). Смотрим, является ли площадь минимальной. Если да, то заносим данные имеющиеся на данном этапе.
5) Таким образом проверяются все точки.

Может кто видит чего попроще?

Сугубо IMHO(но можно попробовать)
I)упорядочить треугольники по площади(1 сочетание - вычисляем S, 2 сочетание - вычисляем S, находим его место и т.д.). Работает, если достаточно памяти для хранения. Первый треугольник содержащий 2 мн-во - твой.
II)Не знаю на счет реализации, но можно найти контур 2 мн-ва, т.е. составить мн-во(из точек 2-го мн-ва) внутри которого и/или на котором лежат все точки 2 мн-ва. И проверять на вхождение в треугольник только их.
ЗЫЖ повторяю сугубо IMHO.

Сначала для множества 2 можно построить описывающий выпуклый многоугольник - это позволит отбросить внутренние точки как множества 2, так и множества 1.

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

Тут тогда возникает еще два вопроса:

1) Каким образом(по какому принципу) строить описывающий выпуклый многоугольник?
2) Как проверять, входит ли точка в этот многоугольник?

Это тебе к поиску.


Это из пункта 2 выходит.
пройди все точки а потом исключай.

можно таким образом:
(тут я предполагаю, что ни одна тройка точек не лежит на одной прямой)
1. выбираем какую-нибудь точку, про которую мы точно можем сказать, что она будет "с наружи", например, можно взять точку с самой большой x-координатой (если таких несколько - то любую)
2. дальше надо провести через нее линию, от которой все остальные точки будут находиться по одну сторону (если мы выбирали так, как описано в первом пункте, но подойдет вертикальная прямая)
3. находим следующую (соседнюю) вершину выпуклого многоугольника: смотрим на пары (a,b) (a - наша выбранная точка, а b - перебираем все, которые есть) и считаем угол между направлением a->b и направлением прямой из пункта 2, выбираем ту b, для которой этот угол наименьший
...
дальше берем за начальную точку b, за начальное направление вектор (b-a) и повторяем процедуру для нахождения третьей точки границы
...
так перебираем всю границу

вместо сравнения углов эффективнее будет сравнивать их синусы, а их можно посчитать через векторное произведение...