Задача №3399. Сад пермского периода
Оранжерея “Сад пермского периода” представляет собой прямоугольный участок для выращивания растений пермского периода. Оранжерея была разбита дорожками на квадраты. В центре каждого квадрата посажено одно растение. Размер квадрата зависит от корневой системы растения.
За год дорожки заросли травой, что затруднило уход за оранжереей. Чтобы при садовых работах не повредить корневую систему какого-либо растения, по имеющемуся расположению растений необходимо восстановить размеры соответствующих им квадратов.
Введем декартову прямоугольную систему координат, начало которой совмещено с левым нижним углом оранжереи. Ось \(Ox\) направлена вдоль нижней границы участка, ось \(Oy\) – вдоль левой. Изначально дорожки были проложены параллельно осям координат. Единичный отрезок удалось выбрать так, что координаты углов каждого из квадратов оказались целыми.
Требуется написать программу, которая по размеру оранжереи и координатам растений определит размеры соответствующих им квадратов.
В первой строке входного файла записаны три натуральных числа: \(W\) – ширина оранжереи, \(H\) – длина оранжереи и \(N\) – количество посаженых растений. В каждой из следующих \(N\) строк расположены по два числа: \(x_i\), \(y_i\) – координаты \(i\)-го растения (\(0 \lt x_i \lt W\), \(0 \lt y_i \lt H\)). Гарантируется, что соответствующие растениям квадраты имеют целую длину стороны и покрывают всю оранжерею.
В выходной файл необходимо вывести \(N\) целых чисел – размеры квадратов, соответствующих растениям. Числа требуется вывести в порядке описания растений во входном файле.
Оранжерея во втором примере соответствует следующему рисунку:
Данная задача содержит пять подзадач. Следующая группа тестируется только при прохождении предыдущей.
\(W = H \leq 10\); \(N \leq 6\). Для оценки данной подзадачи используется соответствующая группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.
\(W, H \leq 20\); \(N \leq 20\). Для оценки данной подзадачи используется соответствующая группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.
\(W, H \leq 1000\); \(N \leq 1000\). Для оценки данной подзадачи используется соответствующая группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.
\(W, H \leq 2\times 10^5\); \(N \leq 2\times 10^5\). Каждый тест для данной подзадачи оценивается отдельно.
\(W, H \leq 2\times 10^{12}\); \(N \leq 2\times 10^5\). Каждый тест для данной подзадачи оценивается отдельно.
4 6 3 1 1 3 1 2 4
2 2 4
8 8 10 4.5 7.5 5.5 7.5 2 6 4.5 6.5 7 7 5 5 6 2 7 5 2 2 5.5 6.5
1 1 4 1 2 2 4 2 4 1