Cod sursa(job #2094229)

Utilizator patcasrarespatcas rares danut patcasrares Data 25 decembrie 2017 12:57:09
Problema Cele mai apropiate puncte din plan Scor 95
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include<fstream>
#include<algorithm>
#define DN 100005
#include<iomanip>
#include<cmath>
#define x first
#define y second
#define INF 1000000000000000000000LL
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
typedef pair<long long,long long> pii;
pii a[DN];
pii r[DN];
pii v[DN];
int n,ps,pd;
long long dist(pii A,pii B)
{
    return (long long)(A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);
}
long long re(int st,int dr)
{
    if(st==dr)
        return INF;
    int m=0;
    int mij=(st+dr)/2;
    long long rez=min(re(st,mij),re(mij+1,dr));
    ps=st;
    pd=mij+1;
    for(int i=st;i<=dr;i++)
        if(ps<=mij&&(pd>dr||a[ps].y<a[pd].y))
        {
            v[i]=a[ps];
            ps++;
        }
        else
        {
            v[i]=a[pd];
            pd++;
        }
    for(int i=st;i<=dr;i++)
        a[i]=v[i];
    for(int i=st;i<=dr;i++)
        if(abs(a[i].x-a[mij].x)<=rez)
        {
            m++;
            r[m]=a[i];
        }
    for(int i=1;i<=m;i++)
        for(int j=max(1,i-7);j<i;j++)
            rez=min(rez,dist(a[i],a[j]));
    return rez;
}
long long t;
int main()
{
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>a[i].x>>a[i].y;
    sort(a+1,a+n+1);
    t=re(1,n);
    fout<<fixed<<setprecision(6)<<sqrt(t);
}