| ENG RUS | Timus Online Judge |
1332. Джинн-бомбардировкиОграничение времени: 1.0 секунды Ограничение памяти: 64 МБ Дольше всех задержался там некий Питирим Шварц, бывший монах и изобретатель подпорки для мушкета, беззаветно трудившийся над проектом джинн-бомбардировок. Суть проекта состояла в сбрасывании на города противника бутылок с джиннами, выдержанными в заточении не менее трех тысяч лет. Хорошо известно, что джинны в свободном состоянии способны только либо разрушать города, либо строить дворцы. Основательно выдержанный джинн (рассуждал Питирим Шварц), освободившись из бутылки, не станет строить дворцов, и противнику придется туго. Некоторым препятствием к осуществлению этого замысла являлось недостаточное количество бутылок с джиннами, но Шварц рассчитывал пополнить запасы глубоким тралением Красного и Средиземного морей. Разработка проекта джинн-бомбардировок перешла в экспериментальную стадию. На полигоне силами дублей научных сотрудников было возведено N городов. Город представляет собой круг фиксированного радиуса r, одинакового для всех городов. Так как М. М. Камноедов выдал для эксперимента всего 1 бутылку с джином, экспериментаторы решили, что чем больше городов будет разрушено, тем лучше для науки. Известно, что джинн разрушает все на расстоянии R от места падения бутылки. Город считается разрушенным, если он целиком попадает в зону разрушения. Перед тем, как проводить эксперимент, необходимо найти максимальное количество городов, которое может быть разрушено силами одного джинна. Исходные данныеВ первой строке содержится число городов N (1 ≤ N ≤ 100). Следующие N строк содержат координаты центров городов xi, yi - целые числа, |xi|, |yi| ≤ 10000. Центры разных городов не совпадают. В последней строке содержатся радиус джинн-поражения R и радиус города r — целые числа (1 ≤ R, r ≤ 10000). РезультатВыведите максимальное количество городов, которое может быть разрушено в результате бомбардировки. Примеры
Автор задачи: Александр Бикбаев Источник задачи: Десятый командный чемпионат школьников Свердловской области по программированию (16 октября 2004 года) Метки: геометрия |