Cod sursa(job #1236170)

Utilizator armandpredaPreda Armand armandpreda Data 1 octombrie 2014 16:48:05
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <fstream>
#include <algorithm>
#include <cmath>

using namespace std;

ifstream fin("cmap.in");
ofstream fout("cmap.out");

const int MAX=100005;
const long long INF=1ll<<60;
struct punct
{
    int x,y;
}v[MAX];
int y[MAX],aux[MAX];

bool cmp(punct i,punct j)
{
    return i.x<j.x;
}
long long dist(int i,int j)
{
    return 1ll*(v[i].x-v[j].x)*(v[i].x-v[j].x)+1ll*(v[i].y-v[j].y)*(v[i].y-v[j].y);
}
long long divide_impera(int st,int dr)
{
    long long ds,dd;
    if(st==dr)
        return INF;
    if(st+1==dr)
    {
        if(v[y[st]].y>v[y[dr]].y)
            y[st]=dr,y[dr]=st;
        return dist(st,dr);
    }
    int mj=(st+dr)/2;
    ds=divide_impera(st,mj);
    dd=divide_impera(mj+1,dr);
    if(dd<ds)ds=dd;
    int i=st,j=mj+1,k=0;
    while(i<=mj and j<=dr)
        if(v[y[i]].y<v[y[j]].y)
            aux[++k]=y[i++];
        else
            aux[++k]=y[j++];
    while(i<=mj)aux[++k]=y[i++];
    while(j<=dr)aux[++k]=y[j++];
    for(i=st;i<=dr;++i)
        y[i]=aux[i-st+1];
    k=0;
    for(i=st;i<=dr;++i)
        if(abs(v[i].x-v[mj].x)<=ds)
            aux[++k]=i;
    for(i=1;i<=k-7;++i)
        for(j=i+1;j<=i+7;++j)
            if(ds>dist(i,j))
                ds=dist(i,j);
    return ds;
}
int main()
{
    int n,i;
    fin>>n;
    for(i=1;i<=n;++i)
    {
        fin>>v[i].x>>v[i].y;
        y[i]=i;
    }
    sort(v+1,v+n+1,cmp);
    fout.precision(6);
    fout<<fixed<<sqrt((double)divide_impera(1,n));
    return 0;
}