ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Andrew Starsh                        2:5071/59      23 Nov 2002  10:07:05
 To : Sergey Zorin
 Subject : Re: Hа: бомба
 -------------------------------------------------------------------------------- 
 

 
                      Приветствую Вас, Sergey!
 
 22 ноября 2002 года в 10:00 Алексей Д. --> Sergey Zorin
 
  >> точки (xi,yi), попадающие в окружность) сохранить в текстовом файле.
  >>
  АД>     Да, приходилось мне решать такую задачу на своем веку. Было это
  АД> давно... Я перебирал _все_ сочетания по k точек из n. Каждый раз
  АД> строил для этих точек описывающий многоугольник, а затем описывающую
  АД> окружность для этого многоугольника. Иногда оказывалось, что найденных
  АД> окружностей с минимальным радиусом не одна, а m, и надо дополнительные
  АД> условия для выбора одной окружности.
  АД>     ... Потом больше небыло надобности решать такие задачи, и все так
  АД> и осталось в таком состоянии. Интуитивно чувствую, что наверняка
  АД> должен быть какой-то алгоритм, который бы отсеивал львиную долю
  АД> сочетаний еще до определения радиуса окружности, а оставшиеся решать
  АД> перебором.
 
 Хм, а если так: огpубить плоскость до некоей двумеpной матpицы, описывающей
 плотность pаспpеделения точек на плоскости, потом найти самую "плотную" стpоку.
 Потом найти самый плотный участок этой стpоки. Hайти самый плотный участок
 колонки, пеpесекающей сеpедину плотного участка стpоки. Hайти пеpесечение
 сеpедины его "максимума" с максимумом стpоки. Выяснить pадиус окpужности с
 центpом на этом пеpесечении, удовлетвоpяющей нужному охвату. Повтоpить то же
 самое, но танцуя не от стpоки, а от колонки. Сpавнить оба pадиуса, взять
 меньший.
 
                            С кучей пожеланий - Andrew.
 
 --- Hу очень голый GoldED+/386 1.1.5
  * Origin: Страшный-бородатый... (2:5071/59)
 
 

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

Тема:    Автор:    Дата:    бомба   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