Cod sursa(job #956260)

Utilizator cdt2013Cont De Teste cdt2013 Data 2 iunie 2013 17:34:04
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <stdio.h>
#include <algorithm>
#include <math.h>

using namespace std;

struct point {
    int x, y;
} x[100100];

void chmin(double &A, double B) {
    if (A - B > 0.000000001)
        A = B;
}

bool sortX(point A, point B) {
    return A.x < B.x;
}

bool sortY(point A, point B) {
    return A.y < B.y;
}

double dist(point A, point B) {
    return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}

double solve(int left, int right) {
    if (left >= right)
        return 1 << 30;
    if (left + 1 == right)
        return dist(x[left], x[right]);
    int med = (left + right) / 2;
    double res = 1 << 30;
    chmin(res, solve(left, med));
    chmin(res, solve(med + 1, right));
    point tmp[10100];
    int i, j, cnt = 0, used;
    for (i = med; i >= left; --i)
        if (x[med].x - x[i].x <= res)
            tmp[++cnt] = x[i];
    for (i = med + 1; i <= right; ++i)
        if (x[i].x - x[med].x <= res)
            tmp[++cnt] = x[i];
    sort(tmp + 1, tmp + cnt + 1, sortY);
    for (i = 1; i <= cnt; ++i)
        for (j = i + 1, used = 1; j <= cnt && used <= 6; ++j, ++used)
            chmin(res, dist(tmp[i], tmp[j]));
    return res;
}

int main() {
    freopen("cmap.in", "r", stdin);
    freopen("cmap.out", "w", stdout);

    //while (1) {
        int N;
        scanf("%d", &N);
    //    if (N == 0)
    //        return 0;
        for (int i = 1; i <= N; ++i)
            scanf("%d%d", &x[i].x, &x[i].y);
        sort(x + 1, x + N + 1, sortX);
        double dist = solve(1, N);
        printf("%.6lf\n", dist);
    //}

    return 0;
}