Входные данные: стандартный ввод Выходные данные: стандартный вывод Ограничения на память: 64 MB Время на тест: 2 секунды Тесты к задаче:Скачать
ЗАДАНИЕ
Маленькие вредные лягушки "ченгайгури" стали в Корее легендарными. По ночам они прыгают по рисовым полям, втаптывая в землю кустики риса, нанося урон посевам. Утром, заметив поврежденные кустики, вам захотелось определить путь той лягушки, которая нанесла наибольший урон. Лягушка всегда прыгает по полю по прямой линии, причем длина каждого прыжка одинакова:
Кустики риса на вашем поле посажены строго вдоль перпендикулярных линий на одинаковом расстоянии друг от друга, как это показано на рис.1. Вредные лягушки проскакали через все ваше поле, причем путь лягушки начинался за пределами поля с одной его стороны, а заканчивался за его пределами с другой стороны, как это показано на рис.2.
По полю может прыгать много лягушек, перепрыгивая от одного рисового кустика к другому. При каждом прыжке лягушка втаптывает в землю очередной кустик риса, как на рис.3. Отметим, что за ночь одно и то же растение может быть затоптано более, чем одной лягушкой. Конечно, вы не сможете увидеть прямые линии, вдоль которых прыгали лягушки, и какие-либо следы их перемещения за пределами поля. Для примера, показанного на рис.3, вы увидите картину поврежденного поля, показанную на рис.4:
Исходя из рис.4, вы сможете восстановить все возможные пути, по которым лягушки могли бы перемещаться через ваше поле. Нас интересуют только те лягушки, которые повредили не менее трех рисовых кустиков при своем перемещении через поле. Таким образом, мы определили понятие "путь лягушки".
Можно заметить, что три пути, показаные на рис.3, являются путями лягушек (имеются также другие возможные пути лягушек). Вертикальный путь, проходящий вниз вдоль столбца 1 мог бы быть путем лягушки, имеющей длину прыжка 4, однако при этом могло быть повреждено только 2 кустика риса, и такой путь нас не интересует. Рассмотрим диагональный путь, проходящий через кустики, находящиеся на пересечении строки 2 и столбца 3, строки 3 и столбца 4, строки 6 и столбца 7. На этом пути находятся три поврежденных кустика, но путь неравномерный и содержит интервалы неравной длины; таким образом, этот путь также не является путем лягушки. Отметим также, что вдоль линии движения лягушки могут встречаться поврежденные кустики, которые не были повреждены именно этой лягушкой (например, кустик в точке (2, 6) на горизонтальном пути вдоль строки 2 на рис.4), и на поле могут находиться поврежденные кустики, происхождение повреждения которых нельзя объяснить никаким путем лягушки.
Рассмотрим все возможные пути лягушек. Ваша программа должна определить количество поврежденных кустиков риса на пути той лягушки, которая повредила больше всех кустиков (то есть нанесла самый большой урон рисовой плантации). На рис. 4 таким мог быть путь вдоль строки 6, а ответом является число 7.
ВВОД
Ваша программа должна читать данные со стандартного ввода. Первая строка содержит два целых числа R и C, задающих соответственно количество строк и столбцов на вашем рисовом поле, 1≤R,C≤5000. Вторая строка содержит одно целое число N - количество поврежденных рисовых кустиков, 3≤N≤5000. Каждая из следующих N строк содержит два целых числа, номер строки (1≤номер строки≤R) и номер столбца (1≤номер столбца≤C), определяющие позицию поврежденного кустика. Эти числа разделяются одним пробелом. Каждый поврежденный кустик описан только один раз.
ВЫВОД
Ваша программа должна выводить ответ в стандартный вывод. Вывод программы должен содержать одну строку с одним числом, равным количеству кустиков, лежащих на пути лягушки, которая нанесла наибольший урон, если такой путь существует. В противном случае, необходимо вывести 0.
Если ваша программа выводит правильный ответ на тест за отведенное время, вы получаете полное количество баллов за этот тест, иначе - вы получаете 0 баллов. аренда автомобилей москва в Каменногорске . отдых в подмосковье