ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Ђ«ҐЄбҐ© „.                           2:5020/400     22 Nov 2002  11:00:40
 To : Sergey Zorin
 Subject : Hа: бомба
 -------------------------------------------------------------------------------- 
 

 > Требуется составить алгоритм-программу для определения наименьшей
 
 окружности
 
 > (центр и минимальный радиус), охватывающий не менее k из n заданных точек
 
 на
 
 > плоскости. Исходные точки на плоскости (x1,y1),(x2,y2)...(xn,yn) задаются
 
 в
 
 > текстовом фале. Результаты расчетов (координаты центра окружности, рудиус
 
 её и
 
 > точки (xi,yi), попадающие в окружность) сохранить в текстовом файле.
 >
 
     Да, приходилось мне решать такую задачу на своем веку. Было это давно...
 Я перебирал _все_ сочетания по k точек из n. Каждый раз строил для этих
 точек
 описывающий многоугольник, а затем описывающую окружность для этого
 многоугольника. Иногда оказывалось, что найденных окружностей с минимальным
 радиусом не одна, а m, и надо дополнительные условия для выбора одной
 окружности.
     ... Потом больше небыло надобности решать такие задачи, и все так и
 осталось
 в таком состоянии. Интуитивно чувствую, что наверняка должен быть какой-то
 алгоритм, который бы отсеивал львиную долю сочетаний еще до определения
 радиуса окружности, а оставшиеся решать перебором.
 
         Алексей Д.
 --- ifmail v.2.15dev5
  * Origin: MTU-Intel ISP (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    бомба   Sergey Zorin   11 Nov 2002 18:57:22   Re: бомба   Mikhail Kalenkov   11 Nov 2002 15:13:17   Re: бомба   Andrey Belyakov   11 Nov 2002 17:01:39   Re^2: бомба   Andrew Starsh   12 Nov 2002 01:55:01   Re: бомба   Rustam Ramazanov   11 Nov 2002 21:21:47   Re: бомба   Andrey Belyakov   11 Nov 2002 21:40:09   Re: бомба   Rustam Ramazanov   12 Nov 2002 19:23:08   бомба   Anton Kuznetsov   12 Nov 2002 00:30:00   Re: бомба   Vokin Andrei   12 Nov 2002 01:30:20   бомба   Anton Kuznetsov   11 Nov 2002 19:53:00   бомба   Dmitriy Gatsura   12 Nov 2002 23:39:20   бомба   Sergey Zorin   15 Nov 2002 21:52:50   бомба   Sasha Pelepeichenko   15 Nov 2002 01:14:46   бомба   Dmitriy Gatsura   18 Nov 2002 00:22:00   бомба   Sasha Pelepeichenko   21 Nov 2002 00:42:12   Hа: бомба   Ђ«ҐЄбҐ© „.   22 Nov 2002 11:00:40   Re: Hа: бомба   Andrew Starsh   23 Nov 2002 10:07:05