(*::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::*) (* Nicolas Pécheux *) (* Saturday, 19 May 2018 *) (* http://cpge.info *) (*::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::*) (*** Deux points les plus proches ***) type point = float * float;; (* Pour vos tests. Vous pouvez modifier. *) let n_points = 10;; let points = let f _ = (-100. +. Random.float 200., -100. +. Random.float 200.) in Array.init n_points f ;; (** Question 1 **) let distance (x1, y1) (x2, y2) = sqrt ((x1 -. x2) ** 2.0 +. (y1 -. y2) ** 2.0) ;; (** Question 2 **) let plus_proches_naif points = let n = Array.length points in let d_min = ref (distance points.(0) points.(1)) in let couple = ref (points.(0), points.(1)) in for i = 0 to n - 2 do for j = i + 1 to n - 1 do let d = distance points.(i) points.(j) in if d < !d_min then begin d_min := d; couple := (points.(i), points.(j)) end done done; !couple ;; (** Question 3 **) (** Question 4 **) let tri_abscisses tab = let cmp (x1, y1) (x2, y2) = if (x1, y1) = (x2, y2) then 0 else if x1 < x2 || x1 = x2 && y1 < y2 then -1 else 1 in Array.stable_sort cmp tab ;; let tri_ordonnees tab = let cmp (x1, y1) (x2, y2) = if (x1, y1) = (x2, y2) then 0 else if y1 < y2 || y1 = y2 && x1 < x2 then -1 else 1 in Array.stable_sort cmp tab ;; (** Question 5 **) let dans_T (x, _) x0 delta = x0 -. delta <= x && x <= x0 +. delta ;; let nb_dans_T tab x0 delta = let cmpt = ref 0 in for i = 0 to Array.length tab - 1 do if dans_T tab.(i) x0 delta then incr cmpt done; !cmpt ;; let selectionne_points_dans_T tab x0 delta = let nb = nb_dans_T tab x0 delta in let res = Array.make nb (-1., -1.) in let k = ref 0 in for i = 0 to Array.length tab - 1 do if dans_T tab.(i) x0 delta then begin res.(!k) <- tab.(i); incr k end done; res ;; (** Question 6 **) let plus_proches_dans_T tab = let n = Array.length tab in assert (n >= 2); let d_min = ref (distance tab.(0) tab.(1)) in let couple = ref (tab.(0), tab.(1)) in tri_ordonnees tab; for i = 0 to (n - 1) do for j = (i + 1) to min (n - 1) (i + 6) do let d = distance tab.(i) tab.(j) in if d < !d_min then begin d_min := d; couple := (tab.(i), tab.(j)) end done done; !couple ;; let rec plus_proches_diviser points = let n = Array.length points in if n <= 3 then (* Cas de base : on peut utiliser la fonction naïve *) plus_proches_naif points else begin tri_abscisses points; let points_G = Array.sub points 0 (n / 2) in let points_D = Array.sub points (n / 2) (n - (n / 2)) in let x0 = fst points.((n / 2) - 1) in let (p1_G, p2_G) = plus_proches_diviser points_G in let d_G = distance p1_G p2_G in let (p1_D, p2_D) = plus_proches_diviser points_D in let d_D = distance p1_D p2_D in let delta = min d_G d_D in let couple = if d_G = delta then (p1_G, p2_G) else (p1_D, p2_D) in let points_dans_T = selectionne_points_dans_T points x0 delta in if Array.length points_dans_T >= 2 then let (p1_T, p2_T) = plus_proches_dans_T points_dans_T in let d_T = distance p1_T p2_T in if d_T < delta then (p1_T, p2_T) else couple else couple end ;;