Cod sursa(job #1264217)

Utilizator smaraldaSmaranda Dinu smaralda Data 15 noiembrie 2014 16:50:49
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include<stdio.h>
#include<math.h>
#include<vector>
#include<algorithm>
using namespace std;

#define LL long long
#define mid (left + right) / 2
const LL INF = 4e18;

struct POINT {
    LL x, y;

    void read() {
        scanf("%lld%d", &x, &y);
    }
};
vector <POINT> p;

LL dist (POINT a, POINT b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

bool cmpX (POINT a, POINT b) {
    return a.x < b.x;
}

bool cmpY (POINT a, POINT b) {
    return a.y < b.y;
}

LL solve (int left, int right) {
    if(right - left + 1 < 2)
        return INF;
    if(right - left + 1 == 2) {
        if(p[left].y > p[right].y)
            swap(p[left], p[right]);

        return dist(p[left], p[right]);
    }

    int i, j;
    LL res = min(solve(left, mid), solve(mid + 1, right));
    vector <POINT> y(right - left + 1);

    merge(p.begin() + left, p.begin() + mid + 1, p.begin() + mid + 1, p.begin() + right + 1, y.begin(), cmpY);
    for(i = 0; i < y.size(); ++ i)
        for(j = i + 1; j < y.size() && j - i <= 8; ++ j)
            res = min(res, dist(y[i], y[j]));
    return res;
}

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

    scanf("%d", &n);
    p.resize(n);
    for(i = 0; i < n; ++ i)
        p[i].read();

    sort(p.begin(), p.end(), cmpX);

    printf("%lf\n", sqrt(solve(0, n - 1)));
    return 0;
}