Cod sursa(job #832836)

Utilizator iuli1505Parasca Iuliana iuli1505 Data 11 decembrie 2012 16:11:46
Problema Cele mai apropiate puncte din plan Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include<cstdio>
#include<vector>
#include<utility>
#include<algorithm>
#include<cmath>
#define tip long long
#define dist(a,b) (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second)
#define nmax 100009
#define punct pair<tip,tip>
#define Abs(x,y) x>y?x-y:y-x

using namespace std;
int n,i;
vector<pair<tip,tip> >X;
pair<tip,tip>Y[nmax];
vector<pair<tip,tip> >::iterator it;
tip a,b,sol,oo;
punct aux;
int crit(punct a, punct b)
{
    return a.second<=b.second;
}
tip solve(int st, int dr)
{
    tip DS, DD;
    int i,j,k;
    if(st==dr-1)return oo;
    if(st==dr-2)
        if(X[st].second<X[st+1].second){aux=X[st];X[st]=X[st+1];X[st+1]=aux;return dist(X[st],X[st+1]);}
    if(st==dr-3)
    {
        sort(X.begin()+st,X.begin()+dr,crit);
        tip ret=dist(X[st],X[st+1]);
        ret=min(ret, dist(X[st+1],X[st+2]));
        ret=min(ret, dist(X[st+2],X[st]));
        return ret;
    }
    int mi=(st+dr)/2;
    tip Mi=X[mi].first;
    DS=solve(st,mi);
    DD=solve(mi,dr);
    DS=min(DS,DD);
    for(i=st,k=st,j=mi;i<mi&&j<dr;)
    {
        if(X[i].second<X[j].second)
            Y[k++]=X[i++];
        else
            Y[k++]=X[j++];
    }
    for(;i<mi;i++,k++)
        Y[k]=X[i];
    for(;j<dr;j++,k++)
        Y[k]=X[j];
    for(i=st,j=st;i<dr;i++)
        if(Abs(X[i].first,Mi)<DS)
            Y[j++]=X[i];
    if(j==st)return DS;
    DD=dist(Y[st],Y[st+1]);
    for(i=st;i<j;i++)
        for(k=i+1;k<j&&k-i<8;k++)
            DD=min(DD,dist(Y[i],Y[k]));
    return min(DS,DD);
}
int main()
{
    freopen("cmap.in","r",stdin);
    freopen("cmap.out","w",stdout);
    scanf("%d", &n);
    for(i=1;i<=n;i++)
    {
        scanf("%lld%lld", &a, &b);
        X.push_back(make_pair(a,b));
    }
    for(i=1,oo=1;i<=62;oo*=2,i++);
    sort(X.begin(),X.end());
    printf("%.6lf", sqrt((double)solve(0,n)));
    return 0;
}