Cod sursa(job #1251776)

Utilizator CostanMiriamCostan Miriam CostanMiriam Data 29 octombrie 2014 21:30:09
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#define inf 1LL<<61

using namespace std;

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

struct data {
    long long x;
    long long y;
}px[100010],py[100010];

int n;

bool cmp1 (const data &a, const data &b) {
    return a.x<b.x;
}

bool cmp2 (const data &a, const data &b) {
    return a.y<b.y;
}

long long dist (data a, data b) {
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}

inline long long minim (long long  a, long long b) {
    return (a<=b?a:b);
}

long long dei (int st, int dr) {
    long long mid,sol;
    int k;
    if (st==dr)
        return inf;
    if (st+1==dr)
        return dist(px[st],px[dr]);
    mid=(st+dr)/2;
    sol=minim(dei(st,mid),dei(mid+1,dr));
    k=0;
    for (int i=st;i<=dr;i++)
        if (px[mid].x-px[i].x<=sol&&px[i].x-px[mid].x<=sol)
            py[++k]=px[i];
    sort (py+1,py+k+1,cmp2);
    for (int i=1;i<=k;i++)
        for (int j=1;j<=7&&j+i<=k;j++)
            sol=minim(sol,dist(py[i],py[i+j]));

    return sol;
}

int main () {

    fin>>n;
    for (int i=1;i<=n;i++)
        fin>>px[i].x>>px[i].y;
    sort (px+1,px+n+1,cmp1);
    fout<<setprecision(6)<<fixed<<sqrt(dei(1,n))<<"\n";

    return 0;
}