On considère le quadrillage donné par les points du plan à coordonnées entières. De ce quadrillage, on ne garde qu'un carré de taille n*n (où n est une puissance de 2), c'est-à-dire l'ensemble des points (x,y) tels que 0 <= x <= n-1 et 0 <= y <= n-1, avec x et y entiers. Une liste L de points de ce carré est donnée. La "zone d'influence" d'un point de L est l'ensemble des points du carrés qui sont strictement plus proches de ce point que de n'importe quel autre point de L (au sens de la distance euclidienne). On demande la taille (le cardinal) de la plus grande zone d'influence.
L'image suivante montre un exemple avec n=4. La liste L contient 3 points représentés par des couleurs vives : le point (1,0) représenté en vert, le point (3,1) représenté en bleu, et le point (1,2) représenté en rouge. Les points hors de cette liste sont colorés selon la zone d'influence à laquelle ils appartiennent, par exemple le point (0,0) est coloré en vert pale car il est dans la zone d'influence du point (1,0). Les deux points blancs n'appartiennent à aucune zone d'influence car deux points de L sont à distance minimales : les points (1,0) et (1,2).
Ici, la plus grand zone d'influence est la zone rouge, qui contient 6 points (les 5 pales et le vif). La réponse attendue est donc 6.
Entrée
L'entrée du programme contient une première ligne indiquant la taille n du carré (qui sera toujours une puissance de 2 inférieure ou égale à 2¹⁴=16384). A la ligne suivante, on donne la liste L des points dont on considère l'influence, sous la forme "xa ya xb yb xc yc..." des coordonnées (entières, entre 0 et n-1 inclus) séparées par des expaces, le tout suivi d'un retour à la ligne. Les points de la liste L seront relativement espacés les uns des autres et ne suivront jamais de structure trop particulière.
Sortie
La sortie du programme doit être le maximum des cardinaux des zones d'influence des points de la liste L, suivi d'un retour à la ligne.
