Conforto para as vacas
Problem
O pasto do fazendeiro John pode ser representado como uma enorme grade 2D de células (um enorme tabuleiro de xadrez). Inicialmente, o pasto está vazio.
O fazendeiro John adicionará N (1≤N≤10
5) vacas ao pasto, uma a uma. A i-ésima vaca ocupa uma célula (x
i,y
i) que é diferente das células ocupadas por todas as outras vacas (0≤x
i, yi≤1000).
Diz-se que uma vaca está "confortável" se ela tiver exatamente três outras vacas na horizontal e na vertical. O fazendeiro John quer contar quantas vacas estão confortáveis em seu pasto. Para cada i no intervalo 1…N, imprima o número total de vacas que estão confortáveis após a i-ésima vaca ser adicionada ao pasto.
Entrada:
A primeira linha contém um único inteiro N. Cada uma das seguintes N linhas contém dois inteiros separados por espaços indicando as coordenadas (x,y) da cela da vaca. É garantido que todas as células são diferentes.
Saída:
A i-ésima linha da saída deve conter o número total de vacas que estão confortáveis após adicionar a i-ésima vaca ao pasto.
Exemplos
| # |
Entrada |
Saída |
Explicação |
| 1 |
8
0 1
10
1 1
1 2
2 1
2 2
3 1
3 2 |
0
0
0
1
0
0
1
2 |
Após as primeiras 4 vacas serem adicionadas, a vaca na cela (1,1) está confortável.
Depois de adicionar as primeiras 7 vacas, a vaca na cela (2,1) está confortável.
Depois de adicionar as primeiras 8 vacas, a vaca nas células (2,1) e (2,2) está confortável. |