Cod sursa(job #2170546)

Utilizator DenisONIcBanu Denis Andrei DenisONIc Data 15 martie 2018 08:04:08
Problema Cele mai apropiate puncte din plan Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <fstream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <iomanip>
#define pii pair<int,int>
#define Nmax 100002
#define ld long double
using namespace std;

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

int n;
pii P[Nmax];

bool comp(pii a,pii b){if (a.first==b.first) return a.second<b.second; return a.first<b.first;}

ld dist(pii a,pii b){
    return sqrt(1LL * (a.first-b.first) * (a.first-b.first) + 1LL * (a.second-b.second) * (a.second-b.second));
}

ld solve(int st,int dr){
    ld mn = 1e13;
    if (st==dr) return 1e13;
    if (st+1==dr) return dist(P[st],P[dr]);

    int mid = (st+dr)/2;
    mn = min(solve(st,mid),solve(mid+1,dr));

    vector<pii> L,R;
    ld VMID = (P[mid].first+P[mid+1].first)/2;
    for(int i=mid;i>=st && abs(VMID-P[i].first)<=mn;i--) L.push_back(P[i]);
    for(int i=mid+1;i<=dr && abs(VMID-P[i].first)<=mn;i++) R.push_back(P[i]);

    sort(L.begin(),L.end(),comp);
    sort(R.begin(),R.end(),comp);

    int a = 0,b = 0;
    while (a<L.size() && b<R.size()){
        mn = min(mn,dist(L[a],R[b]));
        if (L[a]<=R[b]){
            if (b+1<R.size()) mn = min(mn,dist(L[a],R[b]));
            a++;
        }
        else{
            if (a+1<L.size()) mn = min(mn,dist(L[a],R[b]));
            b++;
        }
    }
    return mn;
}

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(12)<<solve(1,n);

    return 0;
}