Curso 2024/2025
typedef pair<float, float> Punto; float distanciaAlCuadrado(const Punto & p1, const Punto & p2) { float a = p2.first - p1.first; float b = p2.second - p1.second; return a * a + b * b; } bool compararY(const Punto & p1, const Punto & p2) { return p1.second < p2.second; } float distanciaAlCuadradoMinima(const vector<Punto> & puntosPorX, const vector<Punto> & puntosPorY) { // A. Si estamos en el caso base de la recursion, terminamos int talla = puntosPorX.size(); if (talla == 2) return distanciaAlCuadrado(puntosPorX[0], puntosPorX[1]); if (talla == 3) return min({distanciaAlCuadrado(puntosPorX[0], puntosPorX[1]), distanciaAlCuadrado(puntosPorX[0], puntosPorX[2]), distanciaAlCuadrado(puntosPorX[1], puntosPorX[2])}); // B. Dividimos los puntos ordenados por X entre la mitad izquierda y la mitad derecha sin perder esa ordenacion int tallaIzquierda = talla / 2; vector<Punto> puntosIzquierdaPorX(puntosPorX.begin(), puntosPorX.begin() + tallaIzquierda), puntosDerechaPorX(puntosPorX.begin() + tallaIzquierda, puntosPorX.end()); // C. Repartimos los puntos ordenados por Y entre la mitad izquierda y la mitad derecha sin perder esa ordenacion vector<Punto> puntosIzquierdaPorY(tallaIzquierda), puntosDerechaPorY(talla - tallaIzquierda); for (int i = 0, j = 0, k = 0; i < talla; i++) if (puntosPorY[i] < puntosDerechaPorX[0]) // A igual X mira Y; no pueden coincidir X e Y puntosIzquierdaPorY[j++] = puntosPorY[i]; else puntosDerechaPorY[k++] = puntosPorY[i]; // D. Llamamos a la funcion recursiva pasandole los puntos de la mitad izquierda ordenados por X y ordenados por Y float minimaIzquierda = distanciaAlCuadradoMinima(puntosIzquierdaPorX, puntosIzquierdaPorY); // E. Llamamos a la funcion recursiva pasandole los puntos de la mitad derecha ordenados por X y ordenados por Y float minimaDerecha = distanciaAlCuadradoMinima(puntosDerechaPorX, puntosDerechaPorY); // F. Creamos un vector con los puntos en la franja central ordenados por Y float minima = min(minimaIzquierda, minimaDerecha); vector<Punto> puntosCentralesPorY; float frontera = puntosIzquierdaPorX[tallaIzquierda - 1].first; for (auto p : puntosPorY) if ( abs(frontera - p.first) < minima ) puntosCentralesPorY.push_back(p); // G. Calculamos distancias entre puntos de la franja central con criterio de parada por distancia vertical for (int i = 0; i < puntosCentralesPorY.size() - 1; i++) for (int j = i + 1; j < puntosCentralesPorY.size() && puntosCentralesPorY[j].second - puntosCentralesPorY[i].second < minima; j++) minima = min(minima, distanciaAlCuadrado(puntosCentralesPorY[i], puntosCentralesPorY[j])); return minima; } float distanciaMinima(const vector<Punto> & puntos) { // 1. Recibimos n puntos en un vector, no necesariamente ordenados if (puntos.size() < 2) throw string("Necesitamos al menos dos puntos."); // 2. Creamos una copia del vector de puntos ordenada por X y, en caso de empate en X, por Y vector<Punto> puntosPorX(puntos); sort(puntosPorX.begin(), puntosPorX.end()); // Usamos operator< de pair para ordenar por X y, en caso de empate, por Y // 3. Detectamos duplicados y terminamos si los hay // Gracias a la ordenacion anterior, si hay dos puntos consecutivos iguales devolvemos 0, // y si no los hay en adelante sabremos que no hay ningun par de puntos iguales for (int i = 0; i < puntosPorX.size() - 1; i++) if (puntosPorX[i] == puntosPorX[i + 1]) return 0; // 4. Creamos una copia del vector de puntos ordenada por Y vector<Punto> puntosPorY(puntos); sort(puntosPorY.begin(), puntosPorY.end(), compararY); // Aqui basta ordenar solo por Y // 5. Llamamos a la funcion recursiva pasandole las dos copias ordenadas return sqrt(distanciaAlCuadradoMinima(puntosPorX, puntosPorY)); }