Cod sursa(job #1657763)

Utilizator alexpetrescuAlexandru Petrescu alexpetrescu Data 20 martie 2016 19:43:02
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.3 kb
#include <cstdio>
#include <cmath>
#include <algorithm>
#define MAXN 100000
struct mycreation{
    int x, y;
}u[MAXN], v[MAXN], aux[MAXN+1];
bool cmp(const mycreation a, const mycreation b){
    if(a.x!=b.x)return a.x<b.x;
    return a.y<b.y;
}
inline int myabs(int x){
    if(x<0)return -x;
    return x;
}
inline long long dist(mycreation a, mycreation b){
    return 1LL*(a.x-b.x)*(a.x-b.x)+1LL*(a.y-b.y)*(a.y-b.y);
}
inline long long min2(long long a, long long b){
    if(a<b)return a;
    return b;
}
inline void swap(int p, int q){
    mycreation e=u[p];
    u[p]=u[q];
    u[q]=e;
}
inline void myMerge(int a, int b, int c){
    int i=a, j=b, k=0;
    while((i<b)&&(j<c)){
        if(u[i].y<u[j].y){
            aux[k++]=u[i];
            i++;
        }else{
            aux[k++]=u[j];
            j++;
        }
    }
    while(i<b){
        aux[k++]=u[i];
        i++;
    }
    while(j<b){
        aux[k++]=u[j];
        j++;
    }
    for(i=0, j=a; i<k; i++, j++){
        u[j]=aux[i];
    }
}
long long baga(int st, int dr){
    if(st+1==dr){
        if(u[dr].y<u[st].y){
            swap(st, dr);
        }
        return dist(v[st], v[dr]);
    }
    if(st+2==dr){
        if(u[dr].y<u[dr-1].y){
            swap(dr-1, dr);
        }
        if(u[dr].y<u[st].y){
            swap(st, dr);
        }
        if(u[dr-1].y<u[st].y){
            swap(st, dr-1);
        }
        return min2(min2(dist(v[st], v[st+1]), dist(v[st], v[st+2])), dist(v[st+1], v[st+2]));
    }
    int m=(st+dr)/2, i, j, k;
    long long ans=min2(baga(st, m), baga(m+1, dr));
    myMerge(st, m+1, dr+1);
    k=0;
    for(i=st; i<=dr; i++){
        if(myabs(v[m].x-u[i].x)<=ans){
            aux[k++]=u[i];
        }
    }
    for(i=1; i<k; i++){
        for(j=i+1; (j<=k)&&(j-i<8); j++){
            ans=min2(ans, dist(aux[i], aux[j]));
        }
    }
    return ans;
}
int main(){
    int n, i;
    FILE *fin, *fout;
    fin=fopen("cmap.in", "r");
    fout=fopen("cmap.out", "w");
    fscanf(fin, "%d", &n);
    for(i=0; i<n; i++){
        fscanf(fin, "%d%d", &v[i].x, &v[i].y);
    }
    std::sort(v, v+n, cmp);
    for(i=0; i<n; i++){
        u[i]=v[i];
    }
    fprintf(fout, "%.6lf\n", sqrt(baga(0, n-1)));
    fclose(fin);
    fclose(fout);
    return 0;
}