Cod sursa(job #1251825)

Utilizator CostanMiriamCostan Miriam CostanMiriam Data 29 octombrie 2014 22:08:34
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 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;
}

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

void intercl (int st, int mid, int dr) {
    int k=0;
    int i=st,j=mid+1;
    while (i<=mid&&j<=dr)
        if (px[i].x<=px[j].x)
            py[++k]=px[i++];
        else
            py[++k]=px[j++];
    for (;i<=mid;i++)
        py[++k]=px[i];
    for (;j<=dr;j++)
        py[++k]=px[j];
    for (i=st;i<=dr;i++)
        px[i]=py[i-st+1];
}

long long dei (int st, int dr) {
    long long mid,sol;
    int k;
    if (st==dr)
        return inf;
    if (st+1==dr){
        intercl(st,st,dr);
        return dist(px[st],px[dr]);
    }
    mid=(st+dr)/2;
    sol=minim(dei(st,mid),dei(mid+1,dr));
    intercl(st,mid,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];
    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;
}