Cod sursa(job #1027009)

Utilizator costel93FMI - Dumea Eduard Constantin costel93 Data 12 noiembrie 2013 12:53:12
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <fstream>
 
using namespace std;
 
struct punct {long long x, y;} v[100002];
 
void minim(double &x, double y) {
    if (x - y > 0.000000001)
        x = y;
}
 
bool cmpx(punct a, punct b) {
    return a.x < b.x;
}
 
bool cmpy(punct a, punct b) {
    return a.y < b.y;
}
 
double dist(punct a, punct b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
 
double dei(int st, int dr) {
    if (st >= dr)
        return 1 << 30;
 
    if (st + 1 == dr)
        return dist(v[st], v[dr]);
 
    int m = (st + dr) / 2;
 
    double min = 1 << 30;
 
    minim(min, dei(st, m));
    minim(min, dei(m + 1, dr));
 
    punct tmp[10100];
    int i, j, cnt = 0, contor;
 
    for (i = st; i <= dr; ++i)
        if (abs(v[m].x - v[i].x) <= min)
            tmp[++cnt] = v[i];
 
    sort(tmp + 1, tmp + cnt + 1, cmpy);
 
    for (i = 1; i <= cnt; ++i)
        for (j = i + 1, contor = 1; j <= cnt && contor <= 6; ++j, ++contor)
            minim(min, dist(tmp[i], tmp[j]));
 
    return min;
}
 
int main() {
 
    ifstream fin("cmap.in");
    freopen("cmap.out", "w", stdout);
 
    int n;
    fin >> n;
 
    for (int i = 1; i <= n; ++i)
        fin >> v[i].x>>v[i].y;
 
    sort(v + 1, v + n + 1, cmpx);
 
    double dist = dei(1, n);
 
    printf("%.6lf\n", dist);
 
    return 0;
}