Cod sursa(job #590526)

Utilizator drywaterLazar Vlad drywater Data 18 mai 2011 00:46:16
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.47 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>
#define INF 4e18
using namespace std;
int n,i,j,vs;
struct punct{long long x; long long y;};
punct x[100001],y[100001],v[100001];
int cmp(punct a,punct b)
{
    if (a.x!=b.x)
    return (a.x<b.x);
    return (a.y<b.y);
}
inline void swap(punct &a,punct &b)
{
    punct aux=a;
    a=b;
    b=aux;
}
long long dist(punct x,punct y)
{
    return (x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y);
}
inline long long min(long long a,long long b)
{
    if (a>b) return b;
    return a;
}
long long apel(int st,int dr)
{
    if (st>=dr-1) return INF;
    if (dr-st==2)
    {
        if (y[st].x>y[st+1].x || (y[st].x==y[st+1].x && y[st].y>y[st+1].y))
            swap(y[st],y[st+1]);
        return dist(x[st],x[st+1]);
    }
    int m=(st+dr)/2;
    long long best=min(apel(st,m),apel(m,dr));
    sort(y+st+1,y+dr,cmp);
    vs=0;
    for (i=st;i<dr;i++)
        if (abs(y[i].y-x[m].x)<=best)
            v[++vs]=y[i];
    for (i=1;i<=vs;i++)
    {
        for (j=i+1;j<=vs && j-i<=7;j++)
            best=min(best,dist(v[i],v[j]));
    }
    return best;
}
int main(void)
{
    freopen("cmap.in","r",stdin);
    freopen("cmap.out","w",stdout);
    scanf("%d",&n);
    for (i=1;i<=n;i++)
        scanf("%lld%lld",&x[i].x,&x[i].y);
    sort(x+1,x+n+1,cmp);
    for (i=1;i<=n;i++)
    {
        y[i].x=x[i].y;
        y[i].y=x[i].x;
    }
    printf("%.6llf",sqrt(apel(1,n+1)));
    return 0;
}