Cod sursa(job #1913453)

Utilizator FlowstaticBejan Irina Flowstatic Data 8 martie 2017 12:54:25
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iomanip>
#define NMAX 10005
#define INF 1<<30
#define FOR(i,a,b) for(int i = a; i<=b;i++)
using namespace std;

ifstream fin("cmap.in");
ofstream fout("cmap.out");

vector < pair <int, int> > v(NMAX), X, Y;

int dist(const pair <int, int>& a, const pair <int, int>& b)
{
    return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}

int go(int st, int dr, vector < pair <int, int> >& X, vector < pair <int, int> >& Y)
{
    if (st >= dr - 1)
        return INF;

    else if (dr - st == 2)
    {
        if (Y[st] > Y[st + 1])
            swap(Y[st], Y[st + 1]);
        return dist(X[st], X[st + 1]);
    }

    int mid = (st + dr) / 2;
    int best = min(go(st, mid, X, Y), go(mid, dr, X, Y));

    sort(Y.begin() + st, Y.begin() + dr);

    int v_size = 0;
    FOR(i,st,dr-1)
        (abs(Y[i].second - X[mid].first) <= best)
            v[v_size ++] = Y[i];

    FOR(i,0,v_size-1)
    {
        for (int j = i + 1; j < v_size && j - i < 8; ++ j)
            best = min(best, dist(v[i], v[j]));
    }
    return best;
}

int main(void)
{
    int N;
    fin>>N;

    X.resize(n), Y.resize(n);
    FOR(i,0,X.size()-1)
        fin>>X[i].first>>X[i].second;

    sort(X.begin(), X.end());
    FOR(i,0,X.size()-1)
        Y[i] = make_pair(X[i].second, X[i].first);

    fout << fixed << setprecision(6) << sqrt(go(0, X.size(), X, Y)) << "\n";
    return 0;
}