Re: бомба

From

Rustam Ramazanov ()

To

Andrey Belyakov

Date

2002-11-12T18:23:08Z

Area

RU.ALGORITHMS

From: Rustam Ramazanov <ramazanoff@univer.kharkov.ua>

AB> Хммм... Кажется можно избежать, посчитав длины
AB> отрезков и упорядочив
AB> их... и начав с самого короткого. Дальше - бинарно.
Нельзя. Тут кроме длин надо хранить и точки между которыми эти отрезки 
проведены. Придется составить матрицу n x n из длин отрезком между 
точками. Потом найти такую подматрицу из k строк и k столбцов (строки и 
столбцы естественно берутся с одинаковыми номерами) чтобы ее норма была 
минимальна. Не помню как эта норма называется, а имеется ввиду 
максимальный элемент матрицы. Это даст k точек, которые надо будет 
охватить окружностью.
Как построить эту окружность я точно не знаю. Центр ее будет лежать на 
серединном перпендикуляре к отрезку соединяющему наиболее удаленные 
точки из выбранных. Причем расстояние от центра окружности до отрезка 
будет не более половины длины отрезка деленного на sqrt(3). Возможно, 
придется строить итеративно.

Рустам.
-- 
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
 * Origin: Talk.ru (2:5020/400)