|
|
Регистрация | << Правила форума >> | FAQ | Пользователи | Календарь | Поиск | Сообщения за сегодня | Все разделы прочитаны |
|
Опции темы | Поиск в этой теме | Опции просмотра |
#1
|
|||
|
|||
задача "Две телевышки"
Всем привет! Имеется задача:
В некоторой стране есть N городов, причем для каждого из них извест-ны его координаты на плоскости. Правительство приняло постановление о необходимости постройки в стране двух телевышек таким образом, чтобы: • каждая из телевышек была построена в некотором городе; • каждый город находился внутри или на границе области покрытия хотя бы одной телевышки. Принимая во внимание, что область покрытия телевышки представляет собой круг с центром в точке, в которой расположена телевышка, и радиу-сом, равным квадратному корню из ее мощности, найдите, как необходимо построить телевышки, чтобы сумма их мощностей была минимальной. Мощ-ность вышки может быть произвольным неотрицательным числом. Может кто знает методику решения такой задачи, или ссылку какую нить дать. Плз!!!! Оч надо!! |
#2
|
||||
|
||||
Помоему элементарная задача. Для простоты представьте, что у вас все города располагаются на одной линии, линия состоит из отрезков каждый из которых является диаметром вашего круга радиоохвата. Расчитать мощность теперь несложно.
Жизнь такова какова она есть и больше никакова. Помогаю за спасибо. |
#3
|
||||
|
||||
Самый простой вариант - перебором.
Некоторые программисты настолько ленивы, что сразу пишут рабочий код. Если вас наказали ни за что - радуйтесь: вы ни в чем не виноваты. |
#4
|
||||
|
||||
Цитата:
Я неправ? Жизнь такова какова она есть и больше никакова. Помогаю за спасибо. |
#5
|
||||
|
||||
Нужно всего 2 (две) телевышки, чтобы они были минимальной мощности и охватили максимально городов (все).
Некоторые программисты настолько ленивы, что сразу пишут рабочий код. Если вас наказали ни за что - радуйтесь: вы ни в чем не виноваты. |
#6
|
|||
|
|||
именно!!!!
|
#7
|
||||
|
||||
я бы сделал так. Пробежал все города и построил бы окружности из них с радиусами мощности. Там где больше всего перекрытий - там строишь вышки (то есть в областях где максимально количество перекрытий). Так как вышки 2, то области должны быть разные. Таким образом покроешь максимальное количество городов, доказывать я думаю это е надо.
Вот тебе модель. Преобразуй в мат выкладки и запрограммируй Нет повести печальнее на свете, чем повесть о заклиневшем Resete. |