Re: бомба

From

Rustam Ramazanov ()

To

Mikhail Kalenkov

Date

2002-11-11T20:21:47Z

Area

RU.ALGORITHMS

From: Rustam Ramazanov <ramazanoff@univer.kharkov.ua>

MK>> Требуется составить алгоритм-программу для
MK> определения наименьшей окружности
MK>> (центр и минимальный радиус), охватывающий не
MK> менее k из n заданных точек на плоскости. 
MK> Достаточно очевидно, что требуемая окружность
MK> окружность будет проходить
MK> через одну из троек заданных точек. Осталось
MK> только перебрать все возможные
MK> тройки точек и найти среди них ту, которая решает
MK> задачу. 

>Если точек очень
MK> много, то нужно сначала
MK> построить выпуклый многоугольних, содержащий все
MK> точки, вершинами которого
MK> являются некоторые из заданных точек. После этого
MK> достаточно перебирать
MK> тройки точек среди вершин многоугольника.
Таким образом можно найти окружность охватывающую все n точек, а в 
задаче нужно не менее k из n. Видимо, остается только полный перебор, 
описанный выше.

Рустам.
-- 
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
 * Origin: Talk.ru (2:5020/400)