Cod sursa(job #1495234)

Utilizator cordun_cristinaCristina Maria Cordun cordun_cristina Data 2 octombrie 2015 19:22:38
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>

using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");

int n;
const long long oo=1000000000000000LL;
const int Max=100005;

pair <long long, long long> q[Max],p[Max];

long long dist(pair<long long, long long> a, pair<long long, long long> b)
{
    return (a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second);
}

long long dei(int l, int r)
{
    if(l==r) return oo;
    if(r-l==1) return dist(p[l],p[r]);
    int m,k=0;
    m=(l+r)/2;
    long long a,b,Min;
    a=dei(r,m);
    b=dei(m+1,l);
    Min=min(a,b);
    for (int i=l;i<=r;i++)
        if(abs(p[i].first-p[m].first)<=Min) q[++k]=make_pair(p[i].second,p[i].first);
    sort(q+1,q+1+k);
    for(int i=1;i<=k;i++)
        for(int j=i+1;j<=k && j<=i+8;j++) Min=min(Min,dist(q[i],q[j]));
    return Min;
}

int main()
{
    f>>n;
    for(int i=1;i<=n;i++) f>>p[i].first>>p[i].second;
    sort(p+1,p+1+n);
    g<<fixed<<setprecision(6)<<sqrt(dei(1,n))<<'\n';
    return 0;
}