Cod sursa(job #1265202)

Utilizator smaraldaSmaranda Dinu smaralda Data 16 noiembrie 2014 21:14:55
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.37 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%lld", &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[left], &p[mid + 1], &p[mid + 1], &p[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]));

    copy(&p[left], &p[right + 1], y.begin());
    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;
}