Час

10:09:27
25 May 2012
Версія для друку

Метелики

prb56

   Мурзик разом зі своїм хазяїном полюбляв прогулянки на повітряній кулі. Крім прогулянок Мурзик полюбляв ще й метеликів, і тому створював власну колекцію їх фотографій. Саме тому, відправляючись у прогулянку на повітряній кулі, він завжди брав з собою фотоапарат, але завжди з іншим об’єктивом, тому і фотографувати він міг прямокутники різних розмірів A x B. Мурзик завжди розміщував фотоапарат так, щоб на фотографіях відображались прямокутники, зі сторонами, паралельними сторонам клумби, які в свою чергу також мали форму прямокутників, у яких дві сторони були паралельні будівлі школи, яка завжди слугувала однією з осей координат.

   Для фотографування метеликів він обирав такі моменти, коли не було поривів вітру і метелики мирно розміщувались на квітах, що росли на клумбі. Метелик вважається сфотографованим, якщо його центр маси попадає на фотографію.

   Яку найбільшу кількість метеликів може сфотографувати Мурзик?


Технічні умови

   Вхідні дані

   У першому рядку через пропуск 2 числа: розміри прямокутника, який може сфотографувати Мурзик A, B. У другому – кількість метеликів N (1 ≤ N105). Далі йде N рядків з координатами центрів мас Xi, Yi кожного з метеликів через пропуск.  Всі вхідні дані натуральні числа, що не перевищують 109.

   
Вихідні дані

   Єдине число – шукана найбільша кількість метеликів на фотографії.


Інформація про задачу

Ліміт часу: 6 секунд
Ліміт пам`яті: 64 MB
Бали за пройдений тест: 7.5
Складність: 81% 6/32
Класифікація: Геометрія

Приклад

Приклад вхідних даних

200 200
5
300 300
400 0
200 100
400 300
0 300

Приклад вихідних даних

3


← Подарунки до 8 Березня Список задач Метелик-санітар →