Cod sursa(job #1411769)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 31 martie 2015 22:21:34
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.06 kb
#include <bits/stdc++.h>

using namespace std;

#define dataType long long

#define Point pair<dataType,dataType>
#define x first
#define y second

const int Nmax = 100000;

dataType dist(Point A, Point B)
{
    return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
}

bool comp(Point A, Point B)
{
    return A.y < B.y;
}

dataType solve(int st, int dr, vector<Point>& points)
{
    if (st >= dr)
        return numeric_limits<dataType>::max();
    else if (st + 1 == dr)
    {
        if (points[st].y > points[dr].y)
            swap(points[st], points[dr]);

        return dist(points[st], points[dr]);
    }

    int m = (st + dr) / 2;
    dataType medianX = points[m].x;
    dataType d1 = solve(st, m, points);
    dataType d2 = solve(m + 1, dr, points);
    dataType  d = min(d1, d2);

    static vector<Point> auxiliar(points.size());

    int i = st, j = m + 1, k = st;

    while (i <= m && j <= dr)
    {
        if (points[i].y <= points[j].y)
            auxiliar[k++] = points[i++];
        else
            auxiliar[k++] = points[j++];
    }

    while (i <= m)  auxiliar[k++] = points[i++];
    while (j <= dr) auxiliar[k++] = points[j++];

    for (int i = st; i <= dr; ++i)
        points[i] = auxiliar[i];

    int dim = 0;

    for (int i = st; i <= dr; ++i)
        if (abs(points[i].x - medianX) <= d)
            auxiliar[dim++] = points[i];

    for (int i = 0; i < dim; ++i)
    {
        int cnt = 8;
        int j = i - 1;

        while (j >= 0 && cnt > 0)
        {
            d = min(d, dist(auxiliar[i], auxiliar[j]));
            j--;
            cnt--;
        }
    }

    return d;
}

double closestPair(vector<Point>& points)
{
    sort(points.begin(), points.end());
    return sqrt(solve(0, points.size() - 1, points));
}

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

    ios_base::sync_with_stdio(false);

    int N;
    in >> N;

    vector<Point> points(N);

    for (int i = 0; i < N; ++i)
        in >> points[i].x >> points[i].y;

    out << fixed << setprecision(6);
    out << closestPair(points) << "\n";

    return 0;
}