Re: бомба

From

Mikhail Kalenkov ()

To

Sergey Zorin

Date

2002-11-11T14:13:17Z

Area

RU.ALGORITHMS

From: "Mikhail Kalenkov" <kalenkov@rinet.ru>

Hello Sergey

> Требуется составить алгоритм-программу для определения наименьшей
окружности
> (центр и минимальный радиус), охватывающий не менее k из n заданных точек
на
> плоскости. Исходные точки на плоскости (x1,y1),(x2,y2)...(xn,yn) задаются
в
> текстовом фале. Результаты расчетов (координаты центра окружности, рудиус
её и
> точки (xi,yi), попадающие в окружность) сохранить в текстовом файле.

Достаточно очевидно, что требуемая окружность окружность будет проходить
через одну из троек заданных точек. Осталось только перебрать все возможные
тройки точек и найти среди них ту, которая решает задачу. Этот алгоритм
крайне неэффективен, но будет, наверное, самым простым и достаточно быстрым
при числе точек порядка 100. Если точек очень много, то нужно сначала
построить выпуклый многоугольних, содержащий все точки, вершинами которого
являются некоторые из заданных точек. После этого достаточно перебирать
тройки точек среди вершин многоугольника.

    Михаил Каленков.




--- ifmail v.2.15dev5
 * Origin: Cronyx Plus ISP (2:5020/400)