\input{../.headers/cours.tex}

\section{Algorithme naïf}

\subsection{Description}

Soit $d = \sqrt{(\ocaml{fst} l_1 - \ocaml{fst} l_0)^2 + (\ocaml{snd} l_1 - \ocaml{snd} l_0)^2}$.


Pour $i \in \llbracket 0, n \llbracket$:
	Pour $j \in \llbracket 0, n \llbracket$:
Si $\sqrt{(\ocaml{fst} l_i - \ocaml{fst} l_j)^2 + (\ocaml{snd} l_i - \ocaml{snd} l_j)^2} < d$, alors 

soit $d = \sqrt{(\ocaml{fst} l_i - \ocaml{fst} l_j)^2 + (\ocaml{snd} l_i - \ocaml{snd} l_j)^2}$.


\subsection{Complexité}

Ya deux \ocaml{for} imbriqués parcourant $n$ éléments, c'est $O(n^2)$ quoi c'est bon


\subsection{Implémentation}

\begin{minted}{ocaml}

let distance p1 p2 = sqrt ( ((fst p1) -. (fst p2))**2 +. ((snd p1) -. (snd p2))**2 )

let naive_min_distance points = 
    let min_distance = ref (distance l.(0) l.(1)) in
    for i = 0 to (Array.length l) do
    for j = 0 to (Array.length l) do
        let d = distance l.(i) l.(j) in
	if d < !min_distance
	then min_distance := d
    !min_distance;;

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 ;;
\end{minted}

{\it C'est tellement plus clair.}

\section{Cas de dimension 1}

On ne regarde ques les distances deux à deux, avec un algorithme à la diviser pour régner.

\begin{itemize}
	\item Cas de base: liste à deux éléments: c'est la distance elle-même:
	\item Récursion: Si la demi-liste à gauche a une distance minimum plus petite, on retourne celle-là, sinon on retourne l'autre.
\end{itemize}

\section{Diviser pour régner trop naïf}


\begin{align*}
	c_2 &= 1 \\
	c_n &= c_{\left\lfloor \frac{n}{2} \right\rfloor} + c_{\left\lceil \frac{n}{2} \right\rceil }\\
\end{align*}

On a un  $O(n)$, sauf que le tri est en  $O(n\lg n)$.

Sauf qu'on a finalement  $O(n^2 \lg n)$, si il y a trop de points à trier.

\section{Stratégie optimale}

\subsection{On a au plus 8 points}


On ne prend plus une bande verticale mais un carré car on a fait le trie sur les x et sur les y. On regarde les points dans ce carré qui peuvent plus proche que delta.
delta = min(d1,d2)
bande = carrée de longueur 2*delta 
Si d1 = d2 =delta , on pourra avoir un point à gauche et un point à droite (trie des abcisses) avec un point en dessous et un point au dessus (trie des ordonnées).
Tous les points sont possibles sauf le centre(car la distance 0 n'est pas possible), soit 9-1 points soit 8 points qui correspondent à "je suis situé à distance delta de mon voisin le plus proche" 

\subsection{Algorithme}

Bon\ldots

\subsection{Complexité}

\begin{align*}
	c_n&= 2c_{\left\lfloor \frac{n}{2} \right\rfloor}+O(n) \\
	\implies &\Theta(n \lg n)
\end{align*}

\subsection{Implémentation}

\inputminted{ocaml}{./td_5_algorithme_final.ml}


\end{document}