Задача на множества Опции

[Justus]

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

[volvo]

To: Justus
объемы множеств какие? Если не очень большие, то полным перебором задача решается элементарно. Если большие - сложнее, будем думать...

[Justus]

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

[volvo]

а в чем заключается метод перебора?

Из первого множества последовательно выбираешь тройки вершин (алгоритм выборки ищи на форуме), и каждую точку из второго множества проверяешь, принадлежит ли она треугольнику (это тоже есть). Если все точки второго множества принадлежат этому треугольнику, то вычисляем его площадь, сравниваем с текущим минимумом, и (если вновь найденная площадь меньше предыдущей) запоминаем координаты вершин и саму площадь... То же самое повторяем для всех комбинаций вершин из первого множества, в результате получаешь либо 0 (нет таких точек), либо координаты вершин и площадь (которая является минимальной)

[Justus]

Спасибо, попробую.