Cod sursa(job #1662836)

Utilizator matericristea88Cristea-Enache Matei matericristea88 Data 25 martie 2016 10:02:47
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>

using namespace std;

struct eu{
    long long x, y;
};
eu v[100001];

long long i,j,n,m,k;
double minim=100000000;

bool sorting (eu a, eu b){
    return a.x < b.x;
}

double dist (eu a, eu b){
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

void divide (long long st, long long dr){
    long long l1, l2, mid, i, j;
    if(dr - st <= 2){
        for(i = st; i < dr; i++)
            for(j = i + 1; j <= dr; j++){
                double x;
                x=dist(v[i], v[j]);
                if(x < minim)
                    minim = x;
                }
        }
    else{
        mid = (dr + st) / 2;
        divide(st, mid);
        divide(mid + 1, dr);
        long long a = 1;
        long long k = max(a, mid - 4), k1 = min(mid + 4, n);
        for(i = k; i < k1; i++)
            for(j = i + 1; j <= k1; j++){
                double x;
                x = dist(v[i], v[j]);
                if(x < minim)
                    minim = x;
                }
        }
    }
int main ()
{
    freopen("cmap.in", "r", stdin);
    freopen("cmap.out", "w", stdout);
    scanf("%lld", &n);
    for(i = 1; i <= n; i++)
        scanf("%lld %lld", &v[i].x, &v[i].y);
    sort (v + 1, v + n + 1, sorting);
    divide (1, n);
    printf ("%.6lf", minim);
    return 0;
}