Algoritmos y Estructuras de Datos (VJ1215)

1. Recibimos n puntos en un vector, no necesariamente ordenados.

   15 10 25 10 20 10 15 15 10 12 3 9 2 7 8 5

   puntos

2. Creamos una copia del vector de puntos ordenada por X y, en caso de empate en X, por Y.
   Coste temporal: O(n log n).

   10 10 10 15 15 15 20 25 7 9 12 5 8 10 2 3

   puntosPorX

3. Detectamos duplicados y terminamos si los hay.
   Coste temporal: O(n).

4. Creamos una copia del vector de puntos ordenada por Y.
   Coste temporal: O(n log n).

   20 25 15 10 15 10 15 10 2 3 5 7 8 9 10 12

   puntosPorY

5. Llamamos a la función recursiva pasándole las dos copias ordenadas.
   Coste temporal: T(n) = 2 T(n/2) + O(n) = O(n log n).

Coste temporal total: O(n log n + n + n log n + n log n) = O(n log n).

1. Si estamos en el caso base de la recursión, terminamos (piensa cómo completar eso).

2. Dividimos los puntos ordenados por X entre la mitad izquierda y la mitad derecha sin perder esa ordenación.
   Coste temporal: O(n).

   10 10 10 15 7 9 12 5	15 15 20 25 8 10 2 3
   puntosIzquierdaPorX	puntosDerechaPorX

3. Repartimos los puntos ordenados por Y entre la mitad izquierda y la mitad derecha sin perder esa ordenación, poniendo en la mitad izquierda y en la mitad derecha los mismos del paso B pero ordenados por Y.
   Coste temporal: O(n), piensa muy bien cómo.

   15 10 10 10 5 7 9 12	20 25 15 15 2 3 8 10
   puntosIzquierdaPorY	puntosDerechaPorY

4. Llamamos a la función recursiva pasándole los puntos de la mitad izquierda ordenados por X y ordenados por Y.
   Coste temporal: T(n/2).

5. Llamamos a la función recursiva pasándole los puntos de la mitad derecha ordenados por X y ordenados por Y.
   Coste temporal: T(n/2).

6. Creamos un vector con los puntos en la franja central ordenados por Y.
   Coste temporal: O(n).

7. Calculamos distancias entre puntos de la franja central con criterio de parada por distancia vertical.
   Coste temporal: O(n).