ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Rustam Ramazanov                     2:5020/400     12 Nov 2002  19:23:08
 To : Andrey Belyakov
 Subject : Re: бомба
 -------------------------------------------------------------------------------- 
 

 AB> Хммм... Кажется можно избежать, посчитав длины
 AB> отрезков и упорядочив
 AB> их... и начав с самого короткого. Дальше - бинарно.
 
 Hельзя. Тут кроме длин надо хранить и точки между которыми эти отрезки 
 проведены. Придется составить матрицу n x n из длин отрезком между 
 точками. Потом найти такую подматрицу из k строк и k столбцов (строки и 
 столбцы естественно берутся с одинаковыми номерами) чтобы ее норма была 
 минимальна. Hе помню как эта норма называется, а имеется ввиду 
 максимальный элемент матрицы. Это даст k точек, которые надо будет 
 охватить окружностью.
 Как построить эту окружность я точно не знаю. Центр ее будет лежать на 
 серединном перпендикуляре к отрезку соединяющему наиболее удаленные 
 точки из выбранных. Причем расстояние от центра окружности до отрезка 
 будет не более половины длины отрезка деленного на sqrt(3). Возможно, 
 придется строить итеративно.
 
 Рустам.
 -- 
 Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
 --- ifmail v.2.15dev5
  * Origin: Talk.ru (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