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.
LAIKO IR ATMINTIES RIBOJIMAI (Python)
- Laiko ribojimas: 1 sek., procesorius: 1GHz.
- Atmintis: 16,000 KB.
PRADINIAI DUOMENYS
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 à 214=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.
REZULTATAI
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.
PAVYZDYSs
PAVYZDYS NR. 1
pradiniai duomenys:
4 1 0 3 1 1 2
rezultatai:
6
PAVYZDYS NR. 2
pradiniai duomenys:
64 24 28 16 48 12 3 63 7 40 9 8 30
rezultatai:
1203
PAVYZDYS NR. 3
pradiniai duomenys:
2048 42 1000 777 1234 2002 1803
rezultatai:
2414522
KOMENTARAI
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 *)
Tik užsiregistravę ir prisijungę galite pateikti šio uždavinio sprendimą.
Registravimasis užims vos keletą minučių, tuomet galėsite svetainėje spręsti uždavinius, juos testuoti bei pateikti jų sprendimus.
Prisijungę gausite iš anksto paruoštas užuominas arba galėsite kreiptis pagalbos į forumą.
Lorsque vous serez connecté(e), vous pourrez voir vos actions ici.
Išsamų sprendimą galėsite pamatyti tik išsprendę uždavinį.