Cod sursa(job #971812)

Utilizator assa98Andrei Stanciu assa98 Data 10 iulie 2013 11:51:39
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.79 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstdlib>
using namespace std;

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

const long long inf=(long long)1000000000000000000;


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

long long dist(sp a,sp b)
{
    return (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;
    for(poz=st;i<=mij&&j<=dr;poz++)
    {
        if(v[i].y<v[j].y)
        {
            aux[poz]=v[i];
            i++;
        }
        else
        {
            aux[poz]=v[j];
            j++;
        }
    }

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

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

long long solve(int st,int dr)
{
    if(dr<=st)
        return inf;
    if(dr==st+8)
    {
        for(int i=st; i<dr; i++)
            for(int j=i+1; j<=dr; j++)
            {
                d=min(d,dist(v[i],v[j]));
                if(v[i].y>v[j].y)
                {
                    sp aux=v[i];
                    v[i]=v[j];
                    v[j]=aux;
                }
            }
        return d;
    }
    int mij=(st+dr)/2;
    long long d=min(solve(st,mij),solve(mij+1,dr));
    merge_it(st,dr,mij);

    vector <sp> f;

    for(int i=st;i<=dr;i++)
        if(abs(v[i].x-v[mij].x)<=d)
            f.push_back(v[i]);

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

    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);
    printf("%lf\n",sqrt((double)solve(1,n)));
    return 0;
}