Cod sursa(job #1948839)

Utilizator caprariuapCaprariu Alin-Paul caprariuap Data 1 aprilie 2017 14:19:40
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 2.18 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <cmath>
#define nmax 100010
#define eps 0.000001
#define inf 3e18

using namespace std;

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

long long n,i;
pair <long long, long long> a[nmax];
vector <pair <long long, long long> > x,y,z;

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);
}

class comp1
{
public:
    bool operator()(pair<long long, long long> A, pair<long long, long long> B)
    {
        return A.first<B.first;
    }
};

class comp2
{
public:
    bool operator()(pair<long long, long long> A, pair<long long, long long> B)
{
    return A.second<B.second;
}
};

long long divide(long long st, long long dr)
{
    if (dr-st+1<=1)
        return inf;
    long long mij=(st+dr)/2;
    long long minim=min(divide(st,mij),divide(mij+1,dr));
    x.clear();
    y.clear();
    for (long long i=mij; i>=st&&minim>=a[mij].first-a[i].first; i--)
        x.push_back(a[i]);
    for (long long i=mij+1; i<=dr&&minim>=a[i].first-a[mij+1].first; i++)
        y.push_back(a[i]);
    sort(x.begin(),x.end(),comp2());
    sort(y.begin(),y.end(),comp2());
    long long j,k;
    j=k=0;
    z.clear();
    while (j<x.size()&&k<y.size())
    {
        if (x[j].second<y[k].second)
            z.push_back(x[j]),j++;
        else
            z.push_back(y[k]),k++;
    }
    while (j<x.size())
        z.push_back(x[j]),j++;
    while (k<y.size())
        z.push_back(y[k]),k++;
    for (j=0; j<z.size()-1; j++)
        for (k=j+1; k<z.size()&&k-j<8; k++)
            minim=min(minim,dist(z[j],z[k]));
//    if (st==1&&dr==n)
//    {
//        for (j=0; j<z.size(); j++)
//            fout << z[j].first << ' ' << z[j].second << '\n';
//        fout << '\n';
//    }
    return minim;
}

int main()
{
    fin >> n;
    for (i=1; i<=n; i++)
        fin >> a[i].first >> a[i].second;
    sort(a+1,a+n+1,comp1());
    fout << fixed << setprecision(7) << (long double)sqrt(divide(1,n)) << '\n';
    fin.close();
    fout.close();
    return 0;
}