Cod sursa(job #1157319)

Utilizator tudgal1001Profir Tudor tudgal1001 Data 28 martie 2014 13:42:46
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<vector>
#define NMax 100005
using namespace std;

vector<pair<long long,long long> > V(NMax),X,Y;

const long long inf=4e18;

long long dist (pair<int,int> A, pair<int,int> B)
{
    return (A.first-B.first)*(A.first-B.first)+(A.second-B.second)*(A.second-B.second);
}

long long modul (long long x)
{
    if (x<0) return -x;
    return x;
}

long long solve (int st, int dr)
{
    int i,j;
    if (st==dr)
        return inf;
    if (dr==st+1)
    {
        if (Y[st]>Y[dr])
            swap(Y[st],Y[dr]);
        return dist(X[st],X[dr]);
    }
    int mij=(st+dr)/2;
    long long best=min(solve(st,mij),solve(mij+1,dr));
    sort(Y.begin()+st,Y.begin()+dr+1);
    int v_size=0;
    for (i=st; i<=dr; i++)
        if (modul(Y[i].second-X[mij].first)<=best)
            V[v_size++]=Y[i];
    for (i=0; i<v_size-1; i++)
        for (j=i+1; j<v_size && j-i<8; j++)
            best=min(best,dist(V[i],V[j]));
    return best;
}

int main ()
{
    int N,x,y,i;
    freopen("cmap.in","r",stdin);
    freopen("cmap.out","w",stdout);
    scanf("%d",&N);
    for (i=1; i<=N; i++)
    {
        scanf("%d%d",&x,&y);
        X.push_back(make_pair(x,y));
    }
    sort(X.begin(),X.end());
    for (i=0; i<X.size(); i++)
        Y.push_back(make_pair(X[i].second,X[i].first));
    printf("%.6lf\n",sqrt(solve(0,X.size()-1)));
    return 0;
}