Cod sursa(job #1026919)

Utilizator R.A.RFMI Romila Remus Arthur R.A.R Data 12 noiembrie 2013 11:09:35
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <fstream>

using namespace std;

const int NMAX = 100002;

class point {
public:

    long long x, y;
} V[NMAX];

void keepMinim(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 divideConquer(int start, int final) {
    if (start >= final)
        return 1 << 30;
    if (start + 1 == final)
        return dist(V[start], V[final]);
    int med = (start + final) / 2;
    double result = 1 << 30;
    keepMinim(result, divideConquer(start, med));
    keepMinim(result, divideConquer(med + 1, final));

    point tmp[10100];
    int i, j, cnt = 0, contor;

    for (i = med; i >= start; --i)
        if (V[med].x - V[i].x <= result)
            tmp[++cnt] = V[i];

    for (i = med + 1; i <= final; ++i)
        if (V[i].x - V[med].x <= result)
            tmp[++cnt] = V[i];

    sort(tmp + 1, tmp + cnt + 1, sortY);

    for (i = 1; i <= cnt; ++i)
        for (j = i + 1, contor = 1; j <= cnt && contor <= 6; ++j, ++contor)
            keepMinim(result, dist(tmp[i], tmp[j]));

    return result;
}

int main() {

    ifstream in("cmap.in");
    freopen("cmap.out", "w", stdout);

    int N;
    in >> N;
    for (int i = 1; i <= N; ++i)
        in >> V[i].x>>V[i].y;
    sort(V + 1, V + N + 1, sortX);
    double dist = divideConquer(1, N);
    printf("%.6lf\n", dist);

    return 0;
}