Cod sursa(job #2188735)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 27 martie 2018 13:43:11
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.59 kb
#include <bits/stdc++.h>
#define INF 4e18
#define ll long long
#define dimn 100005
#define y first
#define x second
typedef std::pair <ll, ll> punct;

int N;
std::vector <std::pair <ll, ll> > X, Y, V(dimn);

std::ifstream f("cmap.in");
std::ofstream g("cmap.out");

ll dist2(punct A, punct  B) {
    return (A.y - B.y)*(A.y - B.y) + (A.x - B.x)*(A.x - B.x);
}

ll divetimp(int st=0, int dr=X.size(), std::vector <punct> &X=X, std::vector <punct> &Y=Y) {
    if(st>=dr - 1)
        return INF;
    if(dr-st == 2) {
        if(Y[st] > Y[st+1])
            std::swap(Y[st], Y[st+1]);
        return dist2(X[st], X[st+1]);
    }

    int m = (st+dr)/2;
    ll min = std::min(divetimp(st, m, X, Y), divetimp(m, dr, X, Y));

    std::merge(Y.begin()+st, Y.begin()+m, Y.begin()+m, Y.begin()+dr, V.begin());
    std::copy(V.begin(), V.begin() + (dr-st), Y.begin()+st);

    int ts = 0;
    for (int i=st; i<dr; i++) {
        if(abs(Y[i].second - X[m].first) <= min)
            V[ts++] = Y[i];
    }

    for(int i=0, j; i<ts; i++) {
        for(j=i+1; j<ts && j-i < 8; j++)
            min = std::min(min, dist2(V[j], V[i]));
    }

    return min;
}

void citire() {
    f >> N;
    int x, y;
    for (int i=1; i<=N; i++) {
        f >> x >> y;
        X.push_back({x, y});
    }
}
void rezolvare() {
    std::sort(X.begin(), X.end());
    for (int i=0; i<N; i++)
        Y.push_back(std::make_pair(X[i].x, X[i].y));

    g << std::fixed << std::setprecision(6) << sqrt(1.0 * divetimp()) << "\n";
}

int main()
{
    citire();
    rezolvare();

    return 0;
}