(* ---------- *)
(* Exercice 1 *)
(* Enveloppe convexe d'un nuage de points *)

(* 1.1 Nuage de points et définitions *)

type point = int * int ;;

(* 1) 21 points *)

let p = Array.make 21 (1,3);;
for i = 1 to 20 do
  let (x, y) = p.(i-1) in
  p.(i) <- x * 17 mod 23, y * 17 mod 19
done;;

let print_point (p : point) : unit =
  let x, y = p in
  print_string "(";
  print_int x;
  print_string ",";
  print_int y;
  print_string ")";
  print_endline "";
;;

(* Test *)

print_point p.(20);;

(* 2) Alignement et fonction alpha *)

let alpha (a : point) (b : point) (c : point) : int =
  let xa, ya = a
  and xb, yb = b
  and xc, yc = c in
  (* ou alors
  (fst b - fst a)*(snd c - snd a) - (fst c - fst a)*(snd b - snd a)
  *)
  (xb - xa) * (yc - ya) - (xc - xa) * (yb - ya)
;;

print_newline ();
for i = 2 to 20 do
  for j = 1 to i-1 do
    for k = 0 to j-1 do
      if alpha p.(i) p.(j) p.(k) = 0
      then begin
        print_string "alignement ";
        print_int k;
        print_string " ";
        print_int j;
        print_string " ";
        print_int i;
        print_newline ()
      end
    done
  done
done;;


(* 3) Point le plus bas, point le plus haut *)

let plus_bas (p : point array) : point =
  let n = Array.length p in
  let a = ref p.(0) in
  for j = 1 to n-1 do
    if (snd !a > snd p.(j))
    || (snd !a = snd p.(j) && fst !a > fst p.(j))
    then a := p.(j)
  done;
  !a
;;


let plus_haut (p : point array) : point =
  let n = Array.length p in
  let a = ref p.(0) in
  for j = 1 to n-1 do
    if (snd !a < snd p.(j))
    || (snd !a = snd p.(j) && fst !a < fst p.(j))
    then a := p.(j)
  done;
  !a
;;

print_endline "Point le plus bas :";;
print_point (plus_bas p);; (* (12, 2) *)

print_endline "Point le plus haut :";;
print_point (plus_haut p);; (* (21, 18) *)


(* 1.2 Une approche "diviser pour régner" *)

(* 4) Séparation en deux nuages de points *)

let rec plus_a_droite (b : point) (h : point) (l : point list) : point * (point list) =
  match l with
    | [] -> b, []
    | t::q ->
  let m, d = plus_a_droite b h q in
  let a = alpha b t h in
  if a <= 0 then
    m, d
  else
    match d with
      | [] -> t, [t]
      | _ ->
        if a > alpha b m h
        then t, t::d
        else m, t::d
;;


(* 5)  *)

let rec quickHull_droite (b : point) (h : point) (l : point list) : point list =
  match plus_a_droite b h l with
  | _, [] -> [b]
  | m, d -> (quickHull_droite b m d)@(quickHull_droite m h d)
  ;;

(* 6) *)

let quickHull (p : point array) : point list =
  let b = plus_haut p in
  let h = plus_bas p in
  let l = Array.to_list p in
  (quickHull_droite b h l) @ (quickHull_droite h b l)
;;


(* ---------- *)
(* Exercice 2 *)

(* 7) *)

let rec nb_inv_tete (x : 'a) (l : 'a list) : int =
  match l with
  | [] -> 0
  | t :: q when x > t -> 1 + nb_inv_tete x q
  | t :: q -> nb_inv_tete x q
;;

let rec nb_inv_naive (liste : 'a list) : int =
  match liste with
  | [] -> 0
  | h :: tl -> (nb_inv_tete h tl) + nb_inv_naive tl
;;

(* Cette version est récursive terminale *)
let rec nb_inv_rectail_aux (acc : int) (liste : 'a list) : int =
  match liste with
  | [] -> 0
  | h :: tl -> nb_inv_rectail_aux (acc + ((nb_inv_tete h tl))) tl
;;
let nb_inv_rectail_naive2 = nb_inv_rectail_aux 0;;


(* 10) *)

let rec scinde_stable (l : 'a list) (i : int) : ('a list * 'a list) =
  if i = 0 then [], l
  else
    let t :: q = l in
    let q1, q2 = scinde_stable q (i-1) in
    t::q1, q2
;;

(* 11) *)

let nb_inv_fus (liste : 'a list) : int =
  let cpt = ref 0 in
  let rec fusion l1 l2 = match l1,l2 with
    | [], _ -> l2
    | _, [] -> l1
    | x1::q1, x2::_ when x1 < x2 ->
      x1 :: (fusion q1 l2)
    | _, x2::q2 ->
      cpt := !cpt + List.length l1;
      x2 :: (fusion l1 q2)
  in
  let rec tri l = match l with
    | [] -> []
    | [x] -> [x]
    | _ ->
      let l1, l2 = scinde_stable l (List.length l/2) in
      fusion (tri l1) (tri l2)
    in
  ignore (tri liste);
  !cpt
;;


(* ---------- *)
(* Exercice 3 *)

(* 12) *)

#load "graphics.cma";;
open Graphics;;
open_graph "";;

(* 13) *)

let rayon = 4;;

let h = (min (size_x () / 23) (size_y () / 19));;

let dilate (a : point) : point =
  let x, y = a in
  (h * x, h * y)
;;

let trace_point (a : point) : unit =
  let x, y = dilate a in
  fill_circle x y rayon
;;

let ecrit (a : point) (chaine : string) : unit =
  let x, y = dilate a in
  moveto x y;
  draw_string chaine
;;

(* Trace le nuage de points *)
clear_graph ();
for i = 0 to 20 do
  trace_point p.(i);
  moveto (fst p.(i)) (snd p.(i));
  ecrit p.(i) (string_of_int i)
done;;

(* 14) *)

let qh = quickHull p;;

draw_poly_line (Array.of_list
(List.map dilate (qh @ [List.hd qh])));;