Cod sursa(job #1423541)

Utilizator linia_intaiConstantinescu Iordache Ciobanu Noi cei din linia intai linia_intai Data 21 aprilie 2015 22:59:37
Problema Cele mai apropiate puncte din plan Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 1.84 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <cmath>

#define NMAX 100005
#define lint long long int
#define inf (1ll << 62)
using namespace std;

struct point {
    int x, y;

    point (int _x = 0, int _y = 0): x(_x), y(_y) {}
};

bool operator< (const point &a, const point &b) {
    if (a.x != b.x)
        return a.x < b.x;
    return a.y < b.y;
}

bool cmp (const point &a, const point &b) {
    if (a.y != b.y)
        return a.y < b.y;
    return a.x < b.x;
}

lint dist (const point &a, const point &b) {
    return 1ll * (a.x - b.x) * (a.x - b.x) + 1ll * (a.y - b.y) * (a.y - b.y);
}

lint closest (vector <point> &points) {
    if (points.size() == 1)
        return inf;

    int middle = (points.size() - 1) / 2;

    vector <point> a;
    for (int i = 0; i <= middle; i++)
        a.push_back(points[i]);

    vector <point> b;
    for (int i = middle + 1; i < points.size(); i++)
        b.push_back(points[i]);

    lint delta = min(closest(a), closest(b));

    a.clear();
    for (int i = 0; i < points.size(); i++)
        if (points[middle].x - delta <= points[i].x && points[i].x <= points[middle].x + delta)
            a.push_back(points[i]);
    sort(a.begin(), a.end(), cmp);

    int j;
    for (int i = 0; i < a.size(); i++)
        for (j = 1; j <= 8 && i + j < a.size(); j++)
            if (dist(a[i], a[i + j]) < delta)
                delta = dist(a[i], a[i + j]);
    return delta;
}

int main()
{
    ifstream cin("cmap.in");
    ofstream cout("cmap.out");

    int n = 0;
    vector <point> v;

    cin >> n;

    int x, y;
    while (n--) {
        cin >> x >> y;

        v.push_back(point(x, y));
    }

    cout << fixed << setprecision(6) << sqrt(closest(v)) << '\n';

    cin.close();
    cout.close();
    return 0;
}