Еще одна сложная задача!!!!

← →
pumba (2002-12-08 09:12) [0]

Сеть сотовой связи состоит из нескольких базовых станций. Сигнал каждой из станций принимается на определенной территории, называемой зоной приема. Зоны приема станций частично пересекаются. Их объединение образует зону приема сети в целом. Размещение базовых станций определяется различными соображениями, прежде всего - рельефом местности и ожидаемым количеством абонентов на данной территории. При этом никакие две станции с пересекающимися зонами приема не могут работать в одном частотном диапазоне. Оператор сотовой связи оплачивает занятые им частотные диапазоны, поэтому заинтересован в минимизации их количества.

Вам дана карта размещения базовых станций и зоны их приема. Зона приема каждой станции представляет собой круг определенного радиуса. Считается, что зоны приема пересекаются, если пересечение соответствующих кругов содержит больше, чем одну точку. Требуется найти минимальное количество частотных каналов, необходимое для работы сети.

Входные данные
Первая строка входного файла содержит целое число N - количество базовых станций (0 < N < 15).

Следующие N строк содержат описания каждой станции: координаты X и Y и радиус зоны приема R, разделенные пробелами. Все координаты целочисленные, 0 < X, Y, R < 16000.

Выходные данные
В выходной файл нужно вывести одно целое число - минимальное количество частотных каналов.

Пример
Входной файл: input.txt
3

1 1 80

100 100 80

50 80 80
Выходной файл: output.txt

3

← →
pumba (2002-12-08 09:41) [1]

!!!!!

Халявщик ты. Однако пять математика. Посмотри на http://algolist.manual.ru/ и http://www.informatik.uni-ulm.de/

Еще одна сложная задача!!!! Найти похожие ветки