eolymp
bolt
Try our new interface for solving problems
Məsələlər

Соседи

Соседи

Рассмотрим прямоугольник на декартовой плоскости с вершинами \textbf{(0, 0)} и \textbf{(w, h)}, где \textbf{w} и \textbf{h} - положительные целые числа. Имеется \textbf{N} пиков гор, расположенных в точках сетки на этом прямоугольнике. Точками сетки называются точки с целыми координатами. Каждый хочет построить дом, но правила таковы: \begin{itemize} \item в каждой точке сетки может быть построено не более одного дома \item нельзя строить дом на пиках гор. \end{itemize} Поэтому имеется \textbf{(w+1)·(h+1)-N} возможных расположений домов. Некоторые из этих расположений считаются лучше, чем другие. Мы говорим, что точка сетки (\textbf{x}, \textbf{y}) имеет северного соседа, если имеется пик в некоторой точке \textbf{(x, y+d)}, где \textbf{d} - положительное число. Аналогично определяются южный, восточный и западный соседи. Таким образом, каждая точка сетки, не являющаяся пиком, может иметь от \textbf{0} до \textbf{4} соседей. Чем больше соседей, тем считается лучше расположение. Подсчитайте сколько точек сетки (не учитывая пики) имеет \textbf{0}, \textbf{1}, \textbf{2}, \textbf{3}, \textbf{4} соседа. Напишите программу, которая \begin{itemize} \item читает описание местности из стандартного ввода \item вычисляет количество точек сетки, имеющих \textbf{0}, \textbf{1}, \textbf{2}, \textbf{3}, \textbf{4} соседа \item выводит результат в стандартный вывод. \end{itemize} \InputFile Первая строка содержит три целых числа \textbf{w}, \textbf{h}, \textbf{N} (\textbf{1} ≤ \textbf{w}, \textbf{h} ≤ \textbf{10^9}), (\textbf{1} ≤ \textbf{N} ≤ \textbf{500000}), разделенных пробелами. Следующие \textbf{N} строк содержат описания размещений пиков. Каждый из них описывается двумя целыми числами \textbf{x} и \textbf{y}(\textbf{0} ≤ \textbf{x} ≤ \textbf{w}), (\textbf{0} ≤ \textbf{y} ≤ \textbf{h}), разделеных одним пробелом. Все пики находятся в различных точках. \OutputFile Первая и единственная строка вывода содержит \textbf{5} целых чисел, ределенных пробелом и обозначающих количество точек решетки (исключая точки пиков), которые имеют ровно \textbf{0}, \textbf{1}, \textbf{2}, \textbf{3}, \textbf{4} соседа.
Zaman məhdudiyyəti 3 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
4 3 6
0 3
2 3
2 1
0 1
3 2
1 2
Çıxış verilənləri #1
1 7 2 3 1

Şərh: Двух соседей имеют точки (3,1) и (3,3), Трех соседей имеют точки (1,1), (0,2), (1,3). Четырех соседей имеет точка (2,2) Ноль соседей имеет точка (4,0) а все остальные точки имеют ровно по одному соседу.