Cod sursa(job #1489277)

Utilizator DeltaMTP Dragos DeltaM Data 20 septembrie 2015 21:37:39
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include<cstdio>
#include<cmath>
#include<algorithm>
#define INF 1LL<<61
using namespace std;
struct pct{
    long long x;
    long long y;
}x[100100],y[100100],z[100100];
int n,i,j;
FILE *f,*g;
int cmp(pct a,pct b){
    return a.x<b.x;
}
long long dt(pct a,pct b){
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
long long minim(long long a,long long b){
    if(a<b)
        return a;
    return b;
}
void intc(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,i,j,k,r;
    if(st==dr)
        return INF;
    if(st==dr-1){
        intc(st,st,dr);
        return dt(x[st],x[dr]);
    }
    mid=(st+dr)/2;
    r=minim( sol( st , mid ) , sol( mid+1 , dr ) );
    intc(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 , dt( z[i] , z[i+j] ) );
        }
    }
    return r;
}
int main(){
    f=fopen("cmap.in","r");
    g=fopen("cmap.out","w");
    fscanf(f,"%d",&n);
    for(i=1;i<=n;i++){
        fscanf(f,"%lld%lld",&x[i].x,&x[i].y);
    }
    sort(x+1,x+n+1,cmp);
    fprintf(g,"%.6lf",sqrt( sol(1,n) ));


    fclose(f);
    fclose(g);
    return 0;
}