ВУЗ:
Составители:
Рубрика:
дают согласия на установку там передатчиков. Более того , эти
небоскрёбы являются преградой на пути распространения сигнала ,
поэтому установки одного передатчика может оказаться
недостаточно. Мэр хочет установить минимальное количество
передатчиков так, чтобы зоны распространения сигнала покрывали
весь город , исключая, возможно, территорию, занимаемую
упомянутыми выше небоскрёбами.
Город Обломов представляет собой прямоугольник кварталов.
Все кварталы имеют форму квадрата равной площади, а ширина
улиц незначительна по сравнению с размерами квартала . Каждый
небоскрёб занимает полностью один квартал.
Каждый квартал (кроме небоскрёбов) имеет единственную
телевизионную антенну точно в центре, и считается охваченным
телевещанием , если существует какой-нибудь передатчик, который
находится в прямой видимости от антенны . Передатчики могут
располагаться только точно в центре квартала .
Сигнал распространяется строго по прямой. Если на пути от
передатчика к антенне сигнал лишь касается небоскрёба, сигнал
доходит до антенны . Других небоскрёбов в городе нет. Квартал, в
котором установлен передатчик, считается охваченным
телевещанием .
Программа должна найти минимальное количество
необходимых передатчиков и указать места их размещения.
Входной файл: INPUT.TXT
Выходной файл: OUTPUT.TXT
Время тестирования: 20 сек/тест
Входные данные:
Страницы
- « первая
- ‹ предыдущая
- …
- 64
- 65
- 66
- 67
- 68
- …
- следующая ›
- последняя »
