[Wital]

Всем привет! Имеется задача:
В некоторой стране есть N городов, причем для каждого из них извест-ны его координаты на плоскости. Правительство приняло постановление о необходимости постройки в стране двух телевышек таким образом, чтобы:
• каждая из телевышек была построена в некотором городе;
• каждый город находился внутри или на границе области покрытия хотя бы одной телевышки.
Принимая во внимание, что область покрытия телевышки представляет собой круг с центром в точке, в которой расположена телевышка, и радиу-сом, равным квадратному корню из ее мощности, найдите, как необходимо построить телевышки, чтобы сумма их мощностей была минимальной. Мощ-ность вышки может быть произвольным неотрицательным числом.
Может кто знает методику решения такой задачи, или ссылку какую нить дать. Плз!!!! Оч надо!!

[Страдалецъ]

Помоему элементарная задача. Для простоты представьте, что у вас все города располагаются на одной линии, линия состоит из отрезков каждый из которых является диаметром вашего круга радиоохвата. Расчитать мощность теперь несложно.

[Aristarh Dark]

Самый простой вариант - перебором.

[Страдалецъ]

Сообщение от Aristarh Dark

Самый простой вариант - перебором.

Зачем перебором? Допустим есть города А,Б,В,Г и расстояние между ними различное. Берем расстояние между городами А и Б, делим пополам Получаем радиус охвата А и Б, затем берем Б и В, для Б радиус известен следовательно надо расчитать радиус для В который равен разнице между радиусом охвата Б и расстоянием между Б и В. Аналогично расчитываем всю цепочку.
Я неправ?

[Aristarh Dark]

Нужно всего 2 (две) телевышки, чтобы они были минимальной мощности и охватили максимально городов (все).

[Wital]

именно!!!!

[Ferra]

я бы сделал так. Пробежал все города и построил бы окружности из них с радиусами мощности. Там где больше всего перекрытий - там строишь вышки (то есть в областях где максимально количество перекрытий). Так как вышки 2, то области должны быть разные. Таким образом покроешь максимальное количество городов, доказывать я думаю это е надо.

Вот тебе модель. Преобразуй в мат выкладки и запрограммируй