Cod sursa(job #1138114)

Utilizator hevelebalazshevele balazs hevelebalazs Data 9 martie 2014 15:46:34
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.56 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define N 100000
#define abs(x) (x<0)?-(x):(x)
#define fr(i,a,b) for(int i=a;i<b;++i)
int n;
int x[N],y[N];
int X[N],Y[N],T[N];

int cmp(const void*a,const void*b){
    return (x[*(int*)a]-x[*(int*)b]);
    }

double dist(int i,int j){
    int dx=x[i]-x[j];
    int dy=y[i]-y[j];
    return sqrt(dx*dx+dy*dy);
    }

double ld(int l,int r){
    double m,M;
    if(r-l+1<=4){
        m=dist(X[l],X[r-1]);
        fr(i,l,r) fr(j,i+1,r){
            if(y[Y[i]]>y[Y[j]]) {int t=Y[i];Y[i]=Y[j];Y[j]=t;}
            M=dist(X[i],X[j]);
            if(M<m) m=M;
            }
        return m;
        }
    int c=(l+r)/2;
    double L=ld(l,c);
    double R=ld(c,r);
    m=L<R?L:R;
    int i=l,j=c,k=l;
    while(i<c&&j<r)T[k++]=Y[y[Y[i]]<y[Y[j]]?i++:j++];
    while(i<c)T[k++]=Y[i++];
    while(j<r)T[k++]=Y[j++];
    fr(i,l,r)Y[i]=T[i];
    k=0;
    fr(i,l,r)if(abs(x[Y[i]]-x[c])<=m) T[k++]=Y[i];
    fr(i,0,k) fr(j,i+1,k){
        if(j-i==7)break;
        M=dist(T[i],T[j]);
        if(M<m) m=M;
        }
    return m;
    }

double ld1(){
    fr(i,0,n)X[i]=i;
    qsort(X,n,sizeof(int),cmp);
    fr(i,0,n)Y[i]=X[i];
    return ld(0,n);
    }

double ld2(){
    double m=dist(0,1);
    fr(i,0,n) fr(j,i+1,n){
        double M=dist(i,j);
        if(M<m) m=M;
        }
    return m;
    }

int main(){
    freopen("cmap.in","r",stdin);
    freopen("cmap.out","w",stdout);
    scanf("%i",&n);
    fr(i,0,n)scanf("%i%i",x+i,y+i);
    printf("%6f",ld1());
    return 0;
    }