Cod sursa(job #837096)

Utilizator calincojCalin Cojocariu calincoj Data 17 decembrie 2012 13:14:58
Problema Cele mai apropiate puncte din plan Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 2.32 kb
#include <cstdio>
#include<deque>
#include<cmath>
#include<utility>
#include<algorithm>
#define tip long long
#define punct pair<tip,tip>
#define X first
#define Y second
#define N 100010
#define dist(U,V) (U.X-V.X)*(U.X-V.X)+(U.Y-V.Y)*(U.Y-V.Y)
using namespace std;
punct A[N],B[N],PC;
deque<punct> Q;
int n,i,crit(punct,punct);
tip x,y,oo,DEI(int,int);
int main()
{
    freopen("cmap.in","r",stdin);
    freopen("cmap.out","w",stdout);
    scanf("%d",&n);
    oo=1000000000;oo*=oo;
    for(i=1;i<=n;i++)
    {
        scanf("%lld%lld",&x,&y);
        A[i]=make_pair(x,y);
    }
    sort(A+1,A+n+1);
    x=DEI(1,n);
    printf("%lf",sqrt((double)x));
    return 0;
}
tip DEI(int st,int dr)
{
    int mi;
    if(st==dr)return oo;
    if(dr==st+1)
    {
        if(A[st].Y>A[dr].Y){B[st]=A[dr];B[dr]=A[st];}
        else {B[st]=A[st];B[dr]=A[dr];}
        return dist(B[st],B[dr]);
    }
    if(dr==st+2)
    {
        mi=st+1;
        if(A[mi].Y<A[st].Y)
        {
            if(A[dr].Y<A[mi].Y){B[st]=A[dr];B[mi]=A[mi];B[dr]=A[st];}
            else if(A[dr].Y<A[st].Y){B[st]=A[mi];B[mi]=A[dr];B[dr]=A[st];}
            else {B[st]=A[mi];B[mi]=A[st];B[dr]=A[dr];}
        }
        else
        {
            if(A[dr].Y<A[st].Y){B[st]=A[dr];B[mi]=A[st];B[dr]=A[mi];}
            else if(A[dr].Y<A[mi].Y){B[st]=A[st];B[mi]=A[dr];B[dr]=A[mi];}
            else {B[st]=A[st];B[mi]=A[mi];B[dr]=A[dr];}
        }
        tip ret=dist(B[st],B[mi]);ret=min(ret,dist(B[st],B[dr]));ret=min(ret,dist(B[mi],B[dr]));
        return ret;
    }
    mi=(st+dr)/2;
    tip xr,d1,d2,d;
    xr=A[mi].X;d1=DEI(st,mi);d2=DEI(mi+1,dr);d=min(d1,d2);
    merge(B+st,B+mi+1,B+mi+1,B+dr+1,A+st,crit);
    copy(A+st,A+dr+1,B+st);
    Q.resize(0);d1=d;
    for(mi=st;mi<=dr;mi++)
    {
        if(B[mi].X<xr-d||B[mi].X>xr+d)continue;
        Q.push_back(B[mi]);
        if(Q.size()==8)
        {
            PC=Q.front();Q.pop_front();
            for(int i=0;i<7;i++)d1=min(d1,dist(PC,Q[i]));
        }
    }
    mi=Q.size();
    while(mi>1)
    {
        PC=Q.front();Q.pop_front();mi--;
        for(int i=0;i<mi;i++)d1=min(d1,dist(PC,Q[i]));
    }
    d=min(d,d1);
    return d;
}
int crit(punct U,punct V)
{
    if(U.Y<V.Y)return 1;
    if(U.Y>V.Y)return 0;
    if(U.X<=V.X) return 1;
    return 0;
}