Cod sursa(job #2150426)

Utilizator VladTiberiuMihailescu Vlad Tiberiu VladTiberiu Data 3 martie 2018 15:49:25
Problema Cele mai apropiate puncte din plan Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 3.05 kb
#include <stdio.h>
#include <stdlib.h>

#define NMax 100003
#define INF 0x3f3f3f3f
#define INFll 1e18
#define ll long long

typedef struct{
    int x;
    int y;
}POINT;

typedef struct{
    int dist;
    int pointX;
    int pointY;
}SEGMENT;

POINT a[NMax],b[NMax];
int n;
ll ANS = INFll;

void merge_sort(POINT a[], int lo, int hi); ///dupa x
void swap(POINT *x, POINT *y);
ll min(ll x, ll y);
ll dist2(POINT x, POINT y);

POINT aux[NMax];
POINT aux2[NMax];
ll solve(int lo, int hi){
    if(lo == hi){
        return INFll;
    }
    if(hi - lo == 1){
        if(b[lo].y > b[hi].y){
            swap(&b[lo],&b[hi]);
        }
        return dist2(a[lo],a[hi]);
    }
    int mid = (lo + hi) / 2;
    ll local_mn = min(solve(lo, mid),solve(mid + 1, hi));

    int nr = 0;
    int l = lo, r = mid + 1;
    while(l <= mid && r <= hi){
        if(b[l].y < b[r].y){
            aux[++nr] = b[l];
            ++l;
        }else{
            aux[++nr] = b[r];
            ++r;
        }
    }
    while(l <= mid){
        aux[++nr] = b[l];
        ++l;
    }
    while(r <= hi){
        aux[++nr] = b[r];
        ++r;
    }

    for(int i = lo, j = 1; i <= hi; ++i){
        b[i] = aux[j++];
    }

    int nr2 = 0;
    for(int i = lo; i <= hi; ++i){
        if(llabs(1LL*b[i].x - a[mid].x) <= local_mn){
            aux2[++nr2] = b[i];
        }
    }

    for(int i = 1; i <= nr2; ++i){
        for(int j = i + 1; j <= nr2 && j < i + 8; ++j){
            local_mn = min(1LL*local_mn,1LL*dist2(aux2[i],aux2[j]));
        }
    }
    return local_mn;
}
int main(){
    FILE *f,*g;
    f = fopen("cmap.in","r");
    g = fopen("cmap.out","w");

    fscanf(f,"%d",&n);
    for(int i = 1; i <= n; ++i){
        fscanf(f,"%d%d",&a[i].x, &a[i].y);
    }

    merge_sort(a, 1, n);

    for(int i = 1; i <= n; ++i){
        b[i].x = a[i].x;
        b[i].y = a[i].y;
    }

    ll ans = solve(1, n);

    fprintf(g,"%.8f\n",sqrt(ans));
    return 0;
}

POINT v[NMax];
void merge_sort(POINT a[], int lo, int hi){
    if(lo == hi){
        return;
    }
    int mid = (lo + hi) / 2;
    merge_sort(a, lo, mid);
    merge_sort(a, mid + 1, hi);

    int nr = 0;
    int l = lo, r = mid + 1;

    while(l <= mid && r <= hi){
        if(a[l].x < a[r].x){
            v[++nr] = a[l];
            ++l;
        }else{
            v[++nr] = a[r];
            ++r;
        }
    }
    while(l <= mid){
        v[++nr] = a[l];
        ++l;
    }
    while(r <= hi){
        v[++nr] = a[r];
        ++r;
    }
    for(int i = lo, t = 1; i <= hi; ++i){
        a[i] = v[t++];
    }
}
void swap(POINT *x, POINT *y){
    POINT aux = *x;
    *x = *y;
    *y = aux;
}
ll min(ll x, ll y){
    if(x < y)
        return x;
    return y;
}
ll dist2(POINT x, POINT y){
    if(x.x == 1 && x.y == 1){
        printf("%d %d\n",y.x,y.y);
    }
    if(y.x == 1 && y.y == 1){
        printf("%d %d\n",x.x,x.y);
    }
    return 1LL*(1LL*x.x - y.x) * (1LL*x.x - y.x) + 1LL*(1LL*x.y - y.y) * 1LL*(1LL*x.y - y.y);
}