type point = {x:float;y:float}

let p1 = {x=0.;y=0.}
let p2 = {x=1.; y=1.}
let distance m1 m2 =
  let x1 = m1.x and y1 = m1.y and x2 = m2.x and y2 = m2.y in
    let result = (x2 -. x1)**2. +. (y2 -. y1)**2. in
  result
;;

let nuage = [|1.0,2.1; 6.4,7.9|] in
  nuage.(1);;

let sample_array = [| {x=57.; y=39.}; {x=83.; y=5.}; {x=8.9; y=5.9}; {x=3.6; y=61.}; {x=79.; y=3.}; 
  {x=9.2; y=2.3}; {x=27.; y=26.}; {x=7.; y=54.}; {x=8.; y=73.}; {x=21.; y=98.} |]


let distance_i nuage i = let min = ref 0. and aux = ref i in
  for j = !aux+1 to Array.length nuage -1 do
    let aux2 = distance nuage.(!aux) nuage.(j) in
      if aux2 < !min then min := aux2
      done;
      !min
;;

let distance_mini nuage = distance_i nuage 0;;

let distance_mini_1D nuage =
  let n = Array.length nuage in
  let min_dist = ref infinity in
  for i = 0 to n - 2 do
    let dist = nuage.(i+1).x -. nuage.(i).x in
    if dist < !min_dist then min_dist := dist
  done;
  !min_dist
;;

(* merge two sorted arrays *)
let fusion_array_h t l m u =
  let aux = Array.make (u-l+1) t.(0) and i = ref l
  and j = ref (m+1) and k = ref 0 in
  while (!i <= m) && (!j <= u) do
    if t.(!i).x < t.(!j).x || (t.(!i).x = t.(!j).x && t.(!i).y < t.(!j).y) then
      begin
        aux.(!k) <- t.(!i);
        i := !i + 1
      end
    else
      begin
        aux.(!k) <- t.(!j);
        j := !j + 1
      end;
    k := !k + 1
  done;
  while (!i <= m) do
    aux.(!k) <- t.(!i);
    i := !i + 1;
    k := !k + 1
  done;
  while (!j <= u) do
    aux.(!k) <- t.(!j);
    j := !j + 1;
    k := !k + 1
  done;
  for x=0 to (!k-1) do
    t.(l+x) <- aux.(x)
  done
;;

let tri_fusion_array_h t =
  let rec tri_fusion_aux t l u =
    if (l < u) then
      begin
        let m = (l+u)/2 in
        tri_fusion_aux t l m;
        tri_fusion_aux t (m+1) u;
        fusion_array_h t l m u;
      end
  in tri_fusion_aux t 0 (Array.length t - 1);
  t
;;

let fusion_v t l m u =
  let aux = Array.make (u-l+1) t.(0) and i = ref l and j = ref (m+1) and k = ref 0 in
  while !i <= m && !j <= u do
    if t.(!i).y <= t.(!j).y || (t.(!i).y = t.(!j).y && t.(!i).x <= t.(!j).x) then begin
      aux.(!k) <- t.(!i);
      i := !i + 1
    end else begin
      aux.(!k) <- t.(!j);
      j := !j + 1
    end;
    k := !k + 1
  done;
  while !i <= m do
    aux.(!k) <- t.(!i);
    i := !i + 1;
    k := !k + 1
  done;
  while !j <= u do
    aux.(!k) <- t.(!j);
    j := !j + 1;
    k := !k + 1
  done;
  for x = 0 to !k-1 do
    t.(l+x) <- aux.(x)
  done
;;
let tri_fusion_v t =
  let rec tri_fusion_v_aux t l u =
    if l < u then begin
      let m = (l+u)/2 in
      tri_fusion_v_aux t l m;
      tri_fusion_v_aux t (m+1) u;
      fusion_v t l m u;
    end
  in tri_fusion_v_aux t 0 (Array.length t - 1);
  t
;;

let separation nuage_h nuage_v =
  let n = Array.length nuage_h in
  let i = ref 0 in
  while !i < n && nuage_v.(!i).x <= nuage_h.(n/2).x do
    i := !i + 1
  done;
  let nuage_g = Array.sub nuage_h 0 (n/2) in
  let nuage_d = Array.sub nuage_h (n/2) (n - n/2) in
  let nuage_vg = Array.sub nuage_v 0 !i in
  let nuage_vd = Array.sub nuage_v !i (n - !i) in
  (nuage_g, nuage_d, nuage_vg, nuage_vd)
;;

(* let (nuage_g, nuage_d, _, _) = t in nuage_g;; *)


let bande_du_plan nuage_h nuage_v delta =
  let n = Array.length (nuage_h) in
  let xmed = nuage_h.(n/2).x and l = ref [] and cpt = ref 0 in
  for i = n-1 downto 0 do
    let x = nuage_v.(i).x in
    if x <= xmed +. delta && x>= xmed -. delta then
      begin
        cpt := !cpt + 1;
        l := nuage_v.(i)::(!l);
      end;
    done;
    let b = Array.make (!cpt) nuage_h.(0) in
    for k = 0 to !cpt - 1 do
      b.(k)<- List.hd(!l);
      l:= List.tl(!l)
    done;
  b
;;

let minimum_bande b delta =
  let n = Array.length(b) and min = ref delta in
  for i = 0 to n-2 do
    let k = ref (i+1) and y = b.(i).y in
      while !k<n && b.(!k).y < y +. !min do
        let d = distance b.(!k) b.(i) in
          if d<(!min) then
            min:= d;
          k:=!k+1
          done;
        done;
        !min
      ;;