Помогите придумать алгоритм! Задача: Даны два множества точек А и Б на плоскости. Выбрать три точки одного множества так, чтобы круг, ограниченный окружностью,проходящий через эти три точки, содержал все точки второго множества и имел минимальню площадь.

Я бы стал делать так... У нас окружность - множество точек плоскости, равноудаленных от заданной точки - цетра окружности. То есть (Xц-X)^2+(Yц-Y)^2=R^2 Через три точки плоскости можно провести единственную окружность. Соответственно ты берешь любые три точки из первого множества, подставляешь их координаты в выражение вместо X и Y. У тебя получается система из трех уравнений с тремя неизвестными - координаты цетра и радиус. И так ты перебираешь все тройки точек из А и получаешь для них окружности. Твоя искомая окружность должна отвечать следующим условиям: 1. Иметь минимальный радиус (а следовательно и площадь круга,ей ограниченного) 2. Содержать внутри себя все точки множества Б. Это проверить можно тоже простым перебором: проходишься по всем точкам множества Б и каждая его точка должна удовлетворять условию (Xц-Xб)^2-(Yц-Yб)^2 меньше либо равно R^2, где в качестве (Xц,Yц,R), берешь координаты проверяемой окружности. Всё... B)

Да, эта идея приходила мне в голову, но Проблема в том, что система не линейных уравнений - а квадратных!

Ты как будто не в МИРЭА учишься а в каком-нибудь историко-архивном...



Пересчитай сам с самого начала, я этой хренью уже года 4 не занимался, мог ошибиться

Добавлено ([mergetime]1115064288[/mergetime]):
в формуле (4) очепятка - вместо Y2 должно быть Y1

ОГРОМНОЕ СПАСИБО, ВСЁ ПРОВЕРЮ. СПАС МОЮ КУРСОВУЮ :)