Cod sursa(job #780546)

Utilizator SchumiDumitru Andrei Georgian Schumi Data 20 august 2012 19:00:10
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include <cassert>
#include <cmath>
#include <cstdio>

#include <algorithm>

using namespace std;

typedef long long int64;

struct puncte {
    int x;
    int y;
};

const int N = 100005;
const int INF = 0x3f3f3f3f;

int n;
puncte punct[N], mijloc[N];

int cmp(puncte a, puncte b)
{
    if (a.x != b.x)
        return a.x < b.x;
    return a.y < b.y;
}

int cmp2(puncte a, puncte b)
{
    if (a.y != b.y)
        return a.y < b.y;
    return a.x < b.x;
}

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

double rezolva(int left, int right)
{
    if (left == right)
        return INF;
    if (left == right - 1)
        return dist(punct[left], punct[right]);

    int mij = left + (right - left) / 2;
    double sol_left = rezolva(left, mij);
    double sol_right = rezolva(mij + 1, right);
    double sol = min(sol_left, sol_right);

    int dim = 0;
    for (int i = left; i <= right; ++i)
        if (punct[mij].x - sol <= punct[i].x && punct[i].x <= punct[mij].x + sol)
            mijloc[++dim] = punct[i];

    sort (mijloc + 1, mijloc + dim + 1, cmp2);
    
    int n = 1;
    for (int i = 1; i <= dim; ++i) {
        while (n <= dim && mijloc[n].y <= mijloc[i].y + sol)
            ++n;
       
        for (int j = i; j < n; ++j)
            for (int k = j + 1; k <= n; ++k)
                sol = min(sol, dist(mijloc[j], mijloc[k]));

        i = n;
    }

    return sol;
}

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

    assert(scanf("%d", &n) == 1);
    for (int i = 1; i <= n; ++i)
        assert(scanf("%d %d", &punct[i].x, &punct[i].y) == 2);

    sort(punct + 1, punct + n + 1, cmp);

    printf("%.12lf", rezolva(1, n));
}