Cod sursa(job #968836)

Utilizator assa98Andrei Stanciu assa98 Data 2 iulie 2013 20:59:54
Problema Cele mai apropiate puncte din plan Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#define abs(a) (a<0)?(-a):a
using namespace std;

struct sp
{
    long long x,y;
} v[100100],aux[100100];

const double inf=1000000000000000.0;

inline bool cmp(const sp &a,const sp &b)
{
    return a.x<b.x;
}

inline bool cmp2(const sp &a,const sp &b)
{
    return a.y<b.y;
}

inline double dist(sp a,sp b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

void merge_it(int st,int dr,int mij)
{
    int i=st;
    int j=mij+1;
    int poz=st;
    for(i,j,poz; i<=mij&&j<=dr; poz++)
    {
        if(v[i].y<v[j].y)
        {
            aux[poz]=v[i];
            i++;
        }
        else
        {
            aux[poz]=v[j];
            j++;
        }
    }

    for(i; i<=mij; i++,poz++)
        aux[poz]=v[i];
    for(j; j<=dr; j++,poz++)
        aux[poz]=v[j];

    for(int  i=st; i<=dr; i++)
        v[i]=aux[i];

}

double solve(int st,int dr)
{
    if(dr<=st)
        return inf;
    double d=inf;
    if(dr-st+1<=3)
    {
        for(int i=st; i<dr; i++)
            for(int j=i+1; j<=dr; j++)
                d=min(d,dist(v[i],v[j]));
        sort(v+st,v+dr+1,cmp2);
        return d;
    }
    int mij=(st+dr)/2;
    int l=v[mij].x;
    d=min(d,solve(st,mij));
    d=min(d,solve(mij+1,dr));
    merge_it(st,dr,mij);
    vector<sp> f;
    long long dd=(long long)d+1;
    for(int i=st; i<=dr; i++)
        if(abs(l-v[i].x)<=dd)
            f.push_back(v[i]);

    for(int i=1; i<f.size(); i++)
        for (int j=i+1; j<f.size()&& j-i<8; ++ j)
            d=min(dist(v[i],v[j]),d);

    return d;
}

int n;

int main()
{
    freopen("cmap.in","r",stdin);
    freopen("cmap.out","w",stdout);
    scanf("%d",&n);
    for(int  i=1; i<=n; i++)
    {
        scanf("%lld%lld",&v[i].x,&v[i].y);
        v[i].x+=1000000000;
        v[i].y+=1000000000;
    }
    sort(v+1,v+n+1,cmp);
    printf("%lf",solve(1,n));
    return 0;
}