На: бомба

From

Алексей Д. ()

To

Sergey Zorin

Date

2002-11-22T10:00:40Z

Area

RU.ALGORITHMS

From: "Алексей Д." <odegtyarenko@ukrtelecom.net>

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

        Алексей Д.



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