Cod sursa(job #3352175)

Utilizator Eric2954Malmare Eric-Mihai Eric2954 Data 24 aprilie 2026 16:48:18
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.36 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

struct Punct {
    double x, y;
};

// Functie pentru patratul distantei (mentine precizia si viteza)
double distSq(Punct p1, Punct p2) {
    return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}

bool cmpX(const Punct &a, const Punct &b) {
    if (a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}

// Vector auxiliar global sau transmis prin referinta pentru interclasare
Punct temp[100005];

double rezolva(int st, int dr, vector<Punct> &P) {
    // Caz de baza: distanta infinita sau calcul direct pentru 2-3 puncte
    if (st >= dr) return 1e18;
    if (dr - st == 1) {
        if (P[st].y > P[dr].y) swap(P[st], P[dr]); // Sortam dupa Y pentru interclasare
        return sqrt(distSq(P[st], P[dr]));
    }

    int mij = st + (dr - st) / 2;
    double mijX = P[mij].x;

    // Divide: calculam delta pentru cele doua jumatati
    double delta = min(rezolva(st, mij, P), rezolva(mij + 1, dr, P));

    // INTERCLASARE (Merge): sortam punctele dupa Y in O(n)
    int i = st, j = mij + 1, k = st;
    while (i <= mij && j <= dr) {
        if (P[i].y < P[j].y) temp[k++] = P[i++];
        else temp[k++] = P[j++];
    }
    while (i <= mij) temp[k++] = P[i++];
    while (j <= dr) temp[k++] = P[j++];
    for (i = st; i <= dr; i++) P[i] = temp[i];

    // COMBINA: Construim banda centrala folosind punctele deja sortate dupa Y
    vector<Punct> banda;
    for (i = st; i <= dr; i++) {
        if (abs(P[i].x - mijX) <= delta) {
            banda.push_back(P[i]);
        }
    }

    // Verificam regula celor 7 puncte
    for (i = 0; i < banda.size(); i++) {
        for (j = i + 1; j < banda.size() && (banda[j].y - banda[i].y) <= delta && (j - i) <= 7; j++) {
            delta = min(delta, sqrt(distSq(banda[i], banda[j])));
        }
    }

    return delta;
}

int main() {
    ifstream fin("puncte.in");
    ofstream fout("puncte.out");

    int n;
    if (!(fin >> n)) return 0;

    vector<Punct> puncte(n);
    for (int i = 0; i < n; i++) fin >> puncte[i].x >> puncte[i].y;

    // Sortarea initiala dupa X este obligatorie
    sort(puncte.begin(), puncte.end(), cmpX);

    fout << fixed << setprecision(6) << rezolva(0, n - 1, puncte) << endl;

    return 0;
}