Cod sursa(job #1275363)

Utilizator TarabanDragosTaraban Dragos-Petru TarabanDragos Data 25 noiembrie 2014 01:29:47
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include<fstream>
#include<iomanip>
#include<cmath>
#include<algorithm>
#define inf 1LL<<61
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
struct pct{
    long long x;
    long long y;
}x[100010],y[100010],z[100100];
int n,i,j;
int cmp(pct a,pct b) {
    return a.x<b.x;
}
long long lg(pct a,pct 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) {
    if(a<b)
        return a;
    return b;
}
void intercl(long long st,long long mid,long long dr) {
    long long i=st,j=mid+1,k=0;
    while(i<=mid&&j<=dr)
        if(x[i].x<=x[j].x)
            y[++k]=x[i++];
        else
            y[++k]=x[j++];
    for(;i<=mid;i++)
        y[++k]=x[i];
    for(;j<=dr;j++)
        y[++k]=x[j];
    for(i=st;i<=dr;i++)
        x[i]=y[i-st+1];
}
long long sol(long long st, long long dr) {
    long long mid,r,i,j,k;
    if(st==dr)
        return inf;
    if(st+1==dr){
        intercl(st,st,dr);
        return lg(x[st],x[dr]);
    }
    mid=(st+dr)/2;
    r=minim(sol(st,mid),sol(mid+1,dr));
    intercl(st,mid,dr);
    k=0;
    for(i=st;i<=dr;i++)
        if(x[mid].x-x[i].x<=r&&x[i].x-x[mid].x<=r)
            z[++k]=x[i];
    for(i=1;i<=k;i++)
        for(j=1;j<=7&&j+i<=k;j++)
            r=minim(r,lg(z[i],z[i+j]));
    return r;
}
int main (){
    f>>n;
    for(i=1;i<=n;i++)
        f>>x[i].x>>x[i].y;
    sort(x+1,x+n+1,cmp);
    g<<setprecision(6)<<fixed<<sqrt(sol(1,n));
    return 0;


}