Cod sursa(job #1913674)

Utilizator FlowstaticBejan Irina Flowstatic Data 8 martie 2017 13:34:15
Problema Cele mai apropiate puncte din plan Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#define NMAX 100050
#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");

typedef pair<long long int,long long int> Point;
Point x[NMAX],y[NMAX],aux[NMAX];

long long int dist(const Point& a, const Point& b)
{
    return 1ll*(a.first - b.first) * (a.first - b.first) + 1ll*(a.second - b.second) * (a.second - b.second);
}

bool Compare(Point a, Point b)
{
    return a.second < b.second || (a.second == b.second && a.first < b.first);
}
long long int CalculateDistance(int st, int dr)
{
    if (st == dr)
        return INF;

    if (dr - st == 1)
    {
        if (y[st].second > y[dr].second)
            swap(y[st], y[dr]);
        return dist(x[st], x[dr]);
    }

    int mid = (st + dr) / 2;
    long long int best = min(CalculateDistance(st, mid), CalculateDistance(mid+1, dr));

    sort(y + st +1, y + dr+1,Compare);

    int poz = 0;
    FOR(i,st,dr)
        if(1ll * (x[mid].first - y[i].first)*(x[mid].first - y[i].first) <= best)
            aux[poz ++] = y[i];

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

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

    FOR(i,1,n)
        fin>>x[i].first>>x[i].second;

    sort(x+1,x+n+1);
    memcpy(y,x,sizeof(y));

    fout << fixed << setprecision(6) << sqrt(CalculateDistance(1,n))<< "\n";
    return 0;
}