Cod sursa(job #2189411)

Utilizator killer301Ioan Andrei Nicolae killer301 Data 28 martie 2018 10:59:31
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 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;}
bool comp2(pii a,pii b){if (a.second==b.second) return a.first<b.first; return a.second<b.second;}


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> V;
    ld VMID = (P[mid].first+P[mid+1].first)/2;
    for(int i=mid;i>=st && abs(VMID-P[i].first)<=mn;i--) V.push_back(P[i]);
    for(int i=mid+1;i<=dr && abs(VMID-P[i].first)<=mn;i++) V.push_back(P[i]);

    sort(V.begin(),V.end(),comp2);

    for (int i=0;i<V.size();i++)
        for (int j=i+1;j<=i+4 && j<V.size();j++)
            mn = min(mn,dist(V[i],V[j]));

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