Sujet 6 (G)

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 grande zone d'influence est la zone rouge, qui contient 6 points (les 5 pales et le vif). La réponse attendue est donc 6.

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.

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.

Squelettes de codes :

(* Ce fichier contient tout ce qu'il faut pour lire les donnees en entree, les
mettre dans des variables, et afficher votre resultat final en sortie. *)

(* On lit la taille n du carre *)
let n = int_of_string (input_line stdin);;

(* fonction pour separer les elements en entree
Il n'est pas necessaire de comprendre cette fonction pour utiliser le programme !*)
let split_spaces chaine =
  let res = ref [] in
  let temp = ref "" in
  for i = 0 to String.length chaine - 1 do
    if chaine.[i]=' '
    then
      begin
        res := !res @ [!temp];
        temp := "";
      end
    else
      temp := !temp ^ (String.sub chaine i 1);
  done;
  res := !res @ [!temp];
  !res;;

let rec build_list = function
  | [] -> []
  | x::y::q -> (int_of_string x,int_of_string y)::(build_list q)
  | _ -> failwith "La liste en entree n'est pas correcte (longueur impaire).";;

let liste_points = build_list (split_spaces (input_line stdin));;

(* liste_points est maintenant une "(int * int) list" de la forme [(xa,ya);(xb,yb);...]
qui contient les coordonnees des points de la liste L *)

(* fonction pour afficher votre solution *)
let affiche_solution i =
  print_int i;
  print_newline();;

(* Mettez apres ceci le corps de votre programme *)
(* N'oubliez pas de terminer par un appel a affiche_solution !*)

(* Debut de votre programme *)


(* Fin de votre programme *)