Cod sursa(job #1495212)

Utilizator cordun_cristinaCristina Maria Cordun cordun_cristina Data 2 octombrie 2015 18:57:26
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <fstream>
#include <algorithm>
#include <cmath>
#include <iomanip>

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

int n;

const long long oo=100000000000000LL;
const int Max=100005;

pair <long long, long long> p[Max],q[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 i, int j)
{
    long long a,b;
    int m;
    if (i==j) return oo;
    if ((j-i)==1) return dist(p[i],p[j]);
    m=(i+j)/2;
    a=dei(i,m);
    b=dei(m+1,j);
    int k=0;
    long long Min=min(a,b);
    for(int i1=i;i1<=j;i1++)
            if(abs(p[i1].first-p[m].first)>Min) q[++k]=p[i1];
    for(int i1=1;i1<=k-1;i1++)
        for(int j1=i1+1;j1<=k;j1++) Min=min(Min, dist(q[i1],q[j1]));
    return Min;
}

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