(* I Introduction *)
(* II Une première solution*)
(* Question 1 fonction distance *)
  
(* Question 2 plus_proches, version naïve *)
  
(* Génération d'un tableau de flottants aléatoires
Un seul paramètre à passer : le nombre n de points *)
let tableau_aleatoire (n : int) : (float * float) array = 
  let xmin = 0. and xmax = 400. and ymin = 0. and ymax = 400. in
  let rep = Array.make n (xmin, ymin) in
  for i = 0 to n - 1
  do
    let x = xmin +. Random.float (xmax -. xmin) in
    let y = ymin +. Random.float (ymax -. ymin) in
    rep.(i) <- (x, y) 
  done ;
  rep ;;

(* Fonction de visualisation du tableau de points.  *)
(* Pour fermer la fenetre ne PAS cliquez sur la croix rouge, mais appuyer sur une touche du clavier *)
(* Pour fermer la fenetre ne PAS cliquez sur la croix rouge, mais appuyer sur une touche du clavier *)
(* Pour fermer la fenetre ne PAS cliquez sur la croix rouge, mais appuyer sur une touche du clavier *)
(* Pour fermer la fenetre ne PAS cliquez sur la croix rouge, mais appuyer sur une touche du clavier *)
(* Pour fermer la fenetre ne PAS cliquez sur la croix rouge, mais appuyer sur une touche du clavier *)
(* Pour fermer la fenetre ne PAS cliquez sur la croix rouge, mais appuyer sur une touche du clavier *)

#require "graphics";;
open Graphics ;;

let affiche (tableau : (float * float) array) : unit =
  let n = Array.length tableau in
  open_graph " 400x400" ;
  (* Dessin d'un quadrillage pour se repérer *)
  for i = 0 to 20
  do
    moveto (20 * i) 0 ;
    lineto (20 * i) 400 ;
  done ;
  for i = 0 to 20
  do
    moveto 0 (20 * i) ;
    lineto 400 (20 * i) ;
  done ;
  
  for i = 0 to n - 1
  do
    draw_circle (int_of_float (fst tableau.(i))) (int_of_float (snd tableau.(i))) 3
  done ;
  let _ = read_key () in () ;
  close_graph () ;;

(* Pour fermer la fenetre ne PAS cliquez sur la croix rouge, mais appuyer sur une touche du clavier *)
(* Pour fermer la fenetre ne PAS cliquez sur la croix rouge, mais appuyer sur une touche du clavier *)
(* Pour fermer la fenetre ne PAS cliquez sur la croix rouge, mais appuyer sur une touche du clavier *)
(* Pour fermer la fenetre ne PAS cliquez sur la croix rouge, mais appuyer sur une touche du clavier *)


let test = tableau_aleatoire 10 ;;

affiche test ;;

plus_proches test ;;


(* Quelle est la complexité de la fonction plus_proches ? Mettre la réponse dans ce commentaire *)

(* Tri fusion à utiliser pour trier le tableau de points suivant les abscisses ou 
les ordonnées croissantes *)
let division (t : 'a array) : ('a array * 'a array) =
  let n = Array.length t in
  let g = Array.make (n / 2) t.(0) and
      d = Array.make (n - n / 2) t.(0) in
  for i = 0 to n / 2 - 1 do
    g.(i) <- t.(i)
  done ;
  for i = n / 2 to n - 1 do
    d.(i - n / 2) <- t.(i)
  done ;
  (g, d) ;;

let fusion (t1 : 'a array) (t2 : 'a array) (ordre : 'a -> 'a -> bool) : 'a array = 
  let n1 = Array.length t1 and n2 = Array.length t2 in
  let t = Array.make (n1 + n2) t1.(0) in
  let i1 = ref (0) and i2 = ref (0) in
  for i = 0 to (n1 + n2 - 1) do
    if !i1 = n1 then
      begin t.(i) <- t2.(!i2) ; incr i2 end
    else if !i2 = n2 then
       begin t.(i) <- t1.(!i1) ; incr i1 end
    else let (e1, e2) = (t1.(!i1), t2.(!i2)) in
     if ordre e1  e2 then
       begin  t.(i) <- e1 ; incr i1 end
      else begin t.(i) <- e2 ; incr i2 end
  done ;
  t ;;

let rec tri_fusion (t : 'a array) (ordre : 'a -> 'a -> bool) : 'a array = 
  if Array.length t <= 1 then t
  else
    begin
    let t1, t2 = division t in
    let t1_trie = tri_fusion t1 ordre and t2_trie = tri_fusion t2 ordre in
    fusion t1_trie t2_trie ordre
    end;;

(* III Diviser pour régner*)
(* Question 4. Fonction seltz *)

(* Question 5 *)

(* Question 6 *)

(* Question 7 La fonction finale *)

(* Justifier rapidement que la complexité de votre fonction est bien O(n*ln(n)) *)

(* Étude d'un tri *)
(* Question 8 *)

(* Question 9 *)

(* Question 10 *)

(* Question 11 *)