Spectre
Зимни Състезания по Информатика, 2011
Time Limit: 1s, Memory Limit: 64MiB
Докато нормалните хора на нейната възраст се записват да карат шофьорски курс, или курс по математика, Ели се записа в програмата на Спектрите - специална група тактически войници, наричани "призраци". Под вещото ръководство на Гейбриъл Тош, тя е готова да изпълни първата си мисия в бунта срещу Арктурус Менгск. Нейната цел е да пусне ядрена бомба в укрепената с бункери база на секретната планета Валхала, където се разработва новото супер-оръжие "Один".

Ели осъзнава, че това да унищожи всички бункери с една единствена ядрена бомба би било трудно, затова решава да разруши възможно най-много такива. Помогнете й в нейното начинание, като по дадено разположението и размера на бункерите, изчислите колко най-много от тях могат да бъдат унищожени, ако Ели пусне бомбата оптимално.

Бункерите можем да си представим като кръгове с радиус r, докато ядрената експлозия – като кръг с радиус R. За да бъде унищожен един бункер, то той трябва изцяло да попадне под кръга на взрива. Бункерите могат да се застъпват (нова технология за многослоево строителство!), но не могат да се припокриват изцяло (тоест няма два бункера с еднакви координати на центровете).

Можем да обобщим задачата по следния начин: дадени са ви N кръга с радиус r и техните координати върху евклидова равнина, както и един кръг с радиус R, по-голям или равен на r. Колко най-много от малките кръгове можете да покриете изцяло с големия кръг?
Вход
На първия ред на стандартния вход ще съдържа целите числа N, R и r, съответно броят бункери, радиусът на експлозията и радиусът на бункерите. На всеки от следващите N реда ще има двойка цели числа Xi, Yi, указващи разположението на i-тия бункер.
Изход
На единствен ред на стандартния изход изведете по едно единствено цяло число – броя бункери, които може да бъдат унищожени при оптимално пускане на бомбата.
Ограничения
  • 1 ≤ N ≤ 1000
  • 1 ≤ rR ≤ 10000
  • -10000 ≤ Xi, Yi ≤ 10000
Примерен Вход Примерен Изход
4 2 1 0 0 0 1 0 2 0 3 3
8 11 7 0 0 1 4 3 2 5 3 -2 -2 -1 0 4 8 0 5 6
В първия пример има 4 бункера и радиусите са съответно 2 и 1. Оптимално да пуснем бомбата или точно върху бункера с център (0, 1), или върху този с координати (0, 2), като така обхващаме изцяло 3 бункера.
Мрън!