Cod sursa(job #2054174)

Utilizator BLz0rDospra Cristian BLz0r Data 1 noiembrie 2017 19:15:43
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.36 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <vector>
using namespace std;

ifstream fin("cmap.in");
ofstream fout("cmap.out");

inline long long sqr(int x) {
    return 1LL * x * x;
}

class Point {

public:

    int x, y;

    Point(){}
    Point(int x, int y) {
        this->x = x;
        this->y = y;
    }

    friend istream& operator>> (istream& in, Point& a) {
        in >> a.x >> a.y;
    }

    friend bool operator< (const Point a, const Point b) {
        return a.x < b.x;
    }

    friend long long dist(const Point a, const Point b) {
        return sqr(a.x - b.x) + sqr(a.y - b.y);
    }
};

vector<Point> puncteX, puncteY, middlePoints;

void customMerge(int st, int mid, int dr, int lineX, long long d) {

    int i = st, j = mid + 1;

    vector<Point> aux;
    while (i <= mid && j <= dr) {

        if (puncteY[i].y <= puncteY[j].y) {

            if (lineX - puncteY[i].x < d)
                middlePoints.push_back(puncteY[i]);

            aux.push_back(puncteY[i]);
            ++i;
        }
        else {

            if (puncteY[j].x - lineX < d)
                middlePoints.push_back(puncteY[j]);

            aux.push_back(puncteY[j]);
            ++j;
        }
    }

    while (i <= mid) {

        if (lineX - puncteY[i].x < d)
                middlePoints.push_back(puncteY[i]);

        aux.push_back(puncteY[i]);
        ++i;
    }

    while (j <= dr) {

        if (puncteY[j].x - lineX < d)
            middlePoints.push_back(puncteY[j]);

        aux.push_back(puncteY[j]);
        ++j;
    }

    for (int i = st, j = 0; j < aux.size(); ++i, ++j) {
        puncteY[i] = aux[j];
    }
}

long long closestPoints(int st, int dr, int t) {
/*
    for (int i = 1; i <= t; ++i)
        cerr << "\t";
    cerr << "Begin: [" << st << ", " << dr << "]\n";
*/
    if (st >= dr) {
        for (int i = 1; i <= t; ++i)
/*        cerr << "\t";
    cerr << "End: [" << st << ", " << dr << "] -> " << 1LL * 1e18 << "\n";
*/
        return 1LL * 1e18;
    }
    if (st + 1 == dr) {
        if (puncteY[st].y > puncteY[dr].y) {
            swap(puncteY[st], puncteY[dr]);
        }
/*        for (int i = 1; i <= t; ++i)
        cerr << "\t";
    cerr << "End: [" << st << ", " << dr << "] -> " << dist(puncteX[st], puncteX[dr]) << "\n";
*/
        return dist(puncteX[st], puncteX[dr]);
    }

    int mid = (st + dr) >> 1;

    long long d1 = closestPoints(st, mid, t + 1);
    long long d2 = closestPoints(mid + 1, dr, t + 1);
    long long d = min(d1, d2);

    customMerge(st, mid, dr, puncteX[mid].x, d);

    for (int i = 0; i < middlePoints.size(); ++i) {
        for (int j = i + 1; j < middlePoints.size(); ++j) {
            d = min(d, dist(middlePoints[i], middlePoints[j]));
        }
    }
    middlePoints.clear();
/*
    for (int i = 1; i <= t; ++i)
        cerr << "\t";
    cerr << "End: [" << st << ", " << dr << "] -> " << d << "\n";
*/
    return d;
}

int main() {

    int n;

    fin >> n;

    puncteX.resize(n);
    puncteY.resize(n);

    for (int i = 0; i < n; ++i) {
        fin >> puncteX[i];
        puncteY[i] = puncteX[i];
    }

    sort(puncteX.begin(), puncteX.end());

    fout << fixed << setprecision(7) << sqrt(closestPoints(1, n, 0));

    return 0;
}