Cod sursa(job #2333427)

Utilizator TudorCaloianCaloian Tudor-Ioan TudorCaloian Data 1 februarie 2019 01:08:04
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>
#define f first
#define s second
#define inf (1<<63)-1
#define pi pair <ll , ll>
#define ll unsigned long long
using namespace std;

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

ll n;
pair <ll, ll> v[100005];

ll dist( pi x, pi y)
{
    return (x.f-y.f)*(x.f-y.f) +(x.s-y.s)*(x.s-y.s);
}

bool cmp( pair<ll,ll> a, pair<ll,ll> b ){
  if( a.s < b.s ) return true;
    if(a.s == b.s) return a.f <  b.f;
    return false;
}

ll cmap(ll left, ll right)
{
    ll ans = inf;
    if(left-right <= 3)
    {
        for(ll i = left; i < right; i++)
            for(ll j = i+1; j <= right; j++)
                ans = min(ans, dist(v[i], v[j]));
        return ans;
    }

    ll mid = (left+right)/2;
    ans = min(cmap(left, mid), cmap(mid+1, right));

    vector <pi> add;
    for(int i = left; i <= right; i++)
        if(abs(v[i].f-v[mid].f) <= ans)
            add.push_back(v[i]);
    sort(add.begin(), add.end(), cmp);


    for(ll i = 0; i < add.size(); i++)
        for(ll j = i+1; j < add.size() && j-i<8; j++)
            ans = min(ans, dist(add[i], add[j]));
    return ans;
}

int main()
{
    fin >> n;
    for(ll i = 1; i <= n; i++)
        fin >> v[i].f >> v[i].s;

    sort(v+1, v+1+n);
    fout << fixed << setprecision(7) << sqrt((double)cmap(1, n));

    return 0;
}