Кратчайший путь
Студент Василий живёт в городе, где улицы образуют правильную сетку кварталов: все кварталы являются квадратами с длиной стороны, равной 100 метрам. Дом Василия располагается в юго-западном углу – точке с координатами (0, 0). Университет располагается в северо-восточном углу – точке с координатами (N, M). ![]() Выйдя утром из дома, Василий идёт в университет. Он движется по улицам, но при этом некоторые кварталы может пересечь также по диагонали, ведущей из юго-западного угла квартала в северо-восточный. Напишите программу, которая вычислит длину кратчайшего маршрута от дома до университета. Входные данные В первой строке находятся два целых числа N и M (0 < N, M ≤ 109) – размер сетки кварталов с запада на восток (по горизонтали) и с юга на север (по вертикали) соответственно. Во второй строке находится целое число K (0 ≤ K ≤ 105) – количество кварталов, через которые можно пройти наискосок. Далее следуют K строк с парами целых положительных чисел x и y, разделённых пробелами – координаты северо-восточных углов таких кварталов (1 ≤ x ≤ N, 1 ≤ y ≤ M). Выходные данные Требуется вывести длину кратчайшего пути от дома Василия до университета в метрах, округлённую до ближайшего целого. Пример Входные данные 3 2 Выходные данные 383 | |||||||
|