работа с массивами
Даны два множества точек на плоскости. Выбрать три различные точки первого множества так, чтобы круг, ограниченный окружностью, проходящей через эти точки, содержал все точки второго множества и имел минимальную площадь.
- Алгоритм не ясен или реализация на Java? от sadovoya, 18 июня 2014 года
По алгоритму.
Три точки однозначно задают единственную окружность, проходящую через них. Крайний случай -- три точки на одной прямой (окружность бесконечного радиуса).
Находишь для окружности радиус и центр. Перебираешь расстояния от центра окружности до всех точек второго множества и сравниваешь с радиусом окружности. Если радиус больше расстояния, следовательно точка внутри окружности. Если все точки попали внутрь окружности, сохраняшь ее радиус. Дальше перебираешь остальные окружности. Если попалась окружность с меньшим радиусом, охватывающим все точки второго множества, то теперь ее радиус сохраняешь как наименьший. И т.д. пока не перебраны все окружности. Минимальный радиус значит и минимальная площадь.
Ясно, что алгоритм очень тормозной, рост времени счета от числа точек резкий.
Возможно лучше использовать методы Монте-Карло (вероятностные), т.е. брать наугад по три точки из первого множества счетное число раз. Но трудно оценить вероятность того, что несколько выборок дают верный ответ...
Либо совершенствуйте предложенный. Я дал так-сказать решение "в лоб".
Три точки однозначно задают единственную окружность, проходящую через них. Крайний случай -- три точки на одной прямой (окружность бесконечного радиуса).
Находишь для окружности радиус и центр. Перебираешь расстояния от центра окружности до всех точек второго множества и сравниваешь с радиусом окружности. Если радиус больше расстояния, следовательно точка внутри окружности. Если все точки попали внутрь окружности, сохраняшь ее радиус. Дальше перебираешь остальные окружности. Если попалась окружность с меньшим радиусом, охватывающим все точки второго множества, то теперь ее радиус сохраняешь как наименьший. И т.д. пока не перебраны все окружности. Минимальный радиус значит и минимальная площадь.
Ясно, что алгоритм очень тормозной, рост времени счета от числа точек резкий.
Возможно лучше использовать методы Монте-Карло (вероятностные), т.е. брать наугад по три точки из первого множества счетное число раз. Но трудно оценить вероятность того, что несколько выборок дают верный ответ...
Либо совершенствуйте предложенный. Я дал так-сказать решение "в лоб".