Cod sursa(job #968814)

Utilizator assa98Andrei Stanciu assa98 Data 2 iulie 2013 20:09:57
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

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

const double inf=1000000000000.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)
{
    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;
    int dd=(int)d+1;
    for(int i=st;i<=dr;i++)
        if(l-v[i].x<=dd)
            f.push_back(v[i]);

    for(int i=1;i<f.size();i++)
        for(int j=i-1;j>=min(i-5,0);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("%d%d",&v[i].x,&v[i].y);
    sort(v+1,v+n+1,cmp);
    printf("%lf",solve(1,n));
    return 0;
}