let min_distance_nuage l = 

    let rec min_1couple l min (a,b) = match l with
        |[] -> min
        |(c,d)::t -> if (abs_float(a-.c)**2. +. abs_float(b-.d)**2.) < min then
                             let min = abs_float(a-.c)**2. +. abs_float(b-.d)**2. in
                             min_1couple t min (a,b)
                         else
                             min_1couple t min (a,b)
        in 

    let rec aux_nuage l min = match l with
        |[] -> min 
        |(a,b)::t -> aux_nuage t (min_1couple t min (a,b))
        in
    
    let mini = abs_float(fst (List.hd l)-. fst (List.hd (List.tl l)))**2. 
                  +. abs_float(snd (List.hd l) -. snd (List.hd (List.tl l)))**2. in
    
    aux_nuage l mini ;;

let scinder l = let rec aux l l1 l2 n = match l with 
| [] -> (l1, l2)
| h::t when n mod 2 = 0 -> aux t (h::l1) l2 (n+1)
| h::t -> aux t l1 (h::l2) (n+1)
in aux l [] [] 0;;

let rec fusionnerx l1 l2 = match l1, l2 with
| [], _  -> l2
| _,  [] -> l1
| (x1,y1)::t1, (x2,y2)::t2 -> if x1 < x2 || ( x1=x2 && y1<y2) 
        then (x1,y1)::(fusionnerx t1 l2)
        else (x2,y2)::(fusionnerx l1 t2);;

let rec fusionnery l1 l2 = match l1, l2 with
| [], _  -> l2
| _,  [] -> l1
| (x1,y1)::t1, (x2,y2)::t2 -> if y1 < y2 || ( y1=y2 && x1<x2) 
        then (x1,y1)::(fusionnery t1 l2)
        else (x2,y2)::(fusionnery l1 t2);;
        
let rec tri_fusionx l = match l with
| []  -> []
| [h] -> [h]
| _   -> let l1, l2 = scinder l in fusionnerx (tri_fusionx l1) (tri_fusionx l2);;

let rec tri_fusiony l = match l with
| []  -> []
| [h] -> [h]
| _   -> let l1, l2 = scinder l in fusionnery (tri_fusiony l1) (tri_fusiony l2);;


(* on définit une fonction distance *)
let distance p1 p2 = 
	let (x1,y1) = p1 and (x2,y2) = p2 in
		(x1 -. x2)**2. +. (y1 -. y2)**2. ;;

(* on doit modifier la fonction scinder pour renvoyer le milieu des abscisses à la scission*)

let split l = 
    let rec aux l n acc = match l with
    | [] -> [], []
    | h::t when n=0 -> (acc, h::t)
    | h::t -> aux t (n-1) (h::acc) in
    let aux2 = let (l1,l2) = aux l (List.length l / 2) [] in
     let (x1,y1)= (List.hd l1) and (x2,y2)= (List.hd l2) in
     ( List.rev l1 , l2 , (x2 -. x1) /. 2.)
    in aux2  ;;


(* on extrait les points de la bande de la liste ly *)
let inbande ly delta m = 
let bas = m -. delta and haut = m +. delta in
let rec parcourt lp = match lp with
	| []-> []
	| (a,b)::t -> if b < bas then parcourt t 
	else if b < haut then (a,b)::parcourt t else []
in parcourt ly;;

(* on cherche la distance minimale linéairement sur une liste non vide à abscisses triées *)

let dmini ls = 
	let rec aux lp pt = match lp with
		| [] -> distance pt (0.,0.)
		| [dg] -> (distance dg pt)
		| h :: t -> let dc = distance h pt in min dc (aux t h)
	in aux (List.tl ls) (List.hd ls);;

(* on crée la fonction qui encapsule tout car on a besoin de lx et ly*)

let minimum_nuage l = let lx=tri_fusionx l in
	let ly=tri_fusiony l in
	
(* on fusionne les min , la liste ne nous intéresse pas *)
let merge m1 m2 m =
 let delta = min m1 m2 in
    let ptsbande = inbande ly delta m 
    in if (List.length ptsbande) > 0 then min (dmini ptsbande) delta else delta 
    (* s'il y a des points dans la bande on prend le min de ces pts et de delta *)
in

(* on finit le tri fusion sans trier mais en faisant remonter les min *)

let rec mininuage l = match l with
	| []  -> 0.
	| [h] -> distance h (0.,0.)
	| _   -> let l1, l2 , m = split l in merge (mininuage l1) (mininuage l2) m

in mininuage lx;;

let test =[ (1.0,2.0);(2.0,4.0);(2.0,6.0);(1.5,1.5);(3.0,2.0);(3.0,2.5)];;

minimum_nuage test;;