(*But de l'algo :
on passe une liste de "lignes en une dimention"
exemple : [(4, 7); (0, 2); (1, 5)]
et on veut "simplifier" ces lignes.*)
let car (a, b) = a ;;
let cdr (a, b) = b ;;
let cmp_int a b = if a = b then 0 else if a > b then 1 else -1;;
type line = int * int ;;
let order_abscisses (a,b) (c,d) = a - c ;;
let solve li =
let rec each a1 b1 acc = function
| [] -> (a1, b1)::acc
| (a2, b2)::tl -> if a2 < b1
  then each a1 b2 acc tl
  else each a2 b2 ((a1, b1)::acc) tl
in let sorted = List.sort order_abscisses li
in each (car (List.hd sorted) ) (cdr (List.hd sorted) ) [] sorted ;;
solve [(4, 7); (0, 2); (1, 5); (-2, -1); (8, 9); (-6, -2)] ;;
let somme li = List.fold_left (fun a b -> a + b) 0 li ;;
let distance li = somme (List.map (fun (a, b) -> b - a) (solve li) );;
distance [(4, 7); (0, 2); (1, 5); (-2, -1); (8, 9); (-6, -2)] ;;
(*la meme mais avec des rectangles, cette fois-ci, notre but est juste de calculer l'aire*)
type rectangle = line * line ;;
let rect_a1 rect1 = car ( car rect1 );;
let rect_a2 rect1 = car ( cdr rect1 );;
let rect_o1 rect1 = cdr ( car rect1 );;
let rect_o2 rect1 = cdr ( cdr rect1 );;
let order_rect f rect1 rect2 = (f rect1) - (f rect2) ;;
let rectangles_in a b r = (rect_a1 r) <= a && (rect_a2 r) >= b;;
let solve_rect li =
let rectangles_tries = List.sort (order_rect rect_a1) li
in let subdivision = List.merge cmp_int
  (List.map rect_a1 rectangles_tries)
  (List.sort cmp_int (List.map rect_a2 rectangles_tries))
in let distance_subdivision a b =
  (* ici on peut optimiser, comme les rectangles sont tries*)
  let rectangles_subdivision = List.filter (rectangles_in a b) rectangles_tries
  in distance (List.map (fun r -> ((rect_o1 r), (rect_o2 r)) ) rectangles_subdivision)
in let rec parcourt_subdivision aire = function
| hd::[] -> aire
| a::b::tl -> parcourt_subdivision ( (b - a) * (distance_subdivision a b) + aire) (b::tl)
in parcourt_subdivision 0 subdivision;;

solve_rect [ ((1, 1), (3, 3)) ; ((0,0), (2,2)) ] ;;