Problem
Le pâturage du fermier John peut être représenté comme une énorme grille 2D de cellules (un immense échiquier). Initialement, le pâturage est vide.
Le fermier John ajoutera N (1≤N≤10
5) vaches au pâturage une par une. La ième vache occupe une cellule (x
i,y
i) différente des cellules occupées par toutes les autres vaches (0≤x
i sub>, y
i≤1000).
Une vache est dite "confortable" si elle a exactement trois autres vaches horizontalement et verticalement. Le fermier John veut compter combien de vaches sont à l'aise dans son pâturage. Pour chaque i dans l'intervalle 1…N, imprimez le nombre total de vaches qui sont à l'aise après l'ajout de la ième vache au pâturage.
Entrée :
La première ligne contient un seul entier N. Chacune des N lignes suivantes contient deux entiers séparés par des espaces indiquant les coordonnées (x,y) de la cellule de la vache. Il est garanti que toutes les cellules sont distinctes.
Sortie :
La ième ligne de la sortie doit contenir le nombre total de vaches qui sont à l'aise après avoir ajouté la ième vache au pâturage.
Exemples
| # |
Entrée |
Sortie |
Explication |
| 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 |
Une fois les 4 premières vaches ajoutées, la vache dans la cellule (1,1) est confortable.
Après avoir ajouté les 7 premières vaches, la vache dans la cellule (2,1) est confortable.
Après avoir ajouté les 8 premières vaches, la vache dans les cellules (2,1) et (2,2) est à l'aise. |