Задача: Комфортабельные коровы
Пастбище Фермера Юрика может рассматриваться как огромная 2D-решётка ячеек (шахматная доска). Изначально пастбище пустое.
Фермер Юрик добавит N (\(1<=N<=10^5\)) коров на пастбище одну за другой. i-ая корова займёт ячейку (xi,yi), которая отличается от ячеек, занятых всеми другими коровами (\(0<=x_i,y_i<=1000\)).
Корова называется "комфортабельной", если она имеет ровно трёх соседей по горизонтали и вертикали. Комфортабельные коровы дают меньше молока, поэтому Фермер Юрик хочет добавлять коров пока нет комфортабельных (включая ту которую он добавит). Заметим, что добавляемые коровы не обязательно должны иметь координаты x и y в интервале \(0…1000\).
Для каждого i в интервале \(1…N\), выведите минимальное количество коров, которое он должен добавить, чтобы не осталось комфортабельных коров, если считать, что на пастбище находятся только коровы \(1…i\).
Входные данные
Первая строка содержит целое число
N. Каждая из следующих
N строк содержит по 2 разделённых пробелом целых числа (
x,
y), указывающих координаты ячейки с коровой.
Выходные данные
Минимальное количество коров, которое Фермер Юрик должен добавить, для каждого
i в интервале
\(1…N\), на отдельной строке.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
9
0 1
1 0
1 1
1 2
2 1
2 2
3 1
3 2
4 1 |
0
0
0
1
0
0
1
2
4 |
Для i=4, Фермер Юрик должен добавить корову в позицию (2,1),
чтобы сделать корову в позиции (1,1) некомфортабельной.
Для i=9, лучшее что Фермер может сделать - добавить коров в позиции (2,0), (3,0), (2,−1), (2,3).
|
Ваш ответ: