Cod sursa(job #1970396)

Utilizator DenisONIcBanu Denis Andrei DenisONIc Data 19 aprilie 2017 12:12:12
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.51 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define Nmax 100001
#define inf 1e9
#define pb push_back
using namespace std;

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

int n;
pair<int,int> P[Nmax];
vector<pair<int,int> > v;

bool comp(pair<int,int> a,pair<int,int> b)
{
    return a.first<b.first;
}

double dist(pair<int,int> x, pair<int,int> y)
{
    return sqrt((long double)(x.first - y.first) * (x.first - y.first) + (long double)(x.second - y.second) * (x.second - y.second));
}

int _abs(int x)
{
    if (x<0)
        return -x;
    return x;
}

bool comp2(pair<int,int> a,pair<int,int> b)
{
    return a.second<b.second;
}

double ctb(int st,int dr)
{
    int mid = (st+dr)/2,med;
    double a,x;
    if (st==dr)
        return inf;
    if (st+1==dr)
        return dist(P[st],P[dr]);
    a = min(ctb(st,mid),ctb(mid+1,dr));

    med = P[mid].first;
    for (int i=st;i<=dr;i++)
    {
        if (_abs(med-P[i].first)<a)
            v.pb(P[i]);
    }
    sort(v.begin(),v.end(),comp2);

    for (int i=0;i<v.size();i++)
    {
        for (int j=i+1;j<min(i+4,(int)v.size());j++)
        {
            x = dist(v[i],v[j]);
            if (x<a)
                a = x;
        }
    }

    v.clear();
    return a;
}

int main()
{
    f>>n;
    for (int i=1;i<=n;i++)
    {
        f>>P[i].first>>P[i].second;
    }

    sort(P+1,P+n+1,comp);

    g<<fixed<<setprecision(8);
    g<<ctb(1,n);
    return 0;
}