Cod sursa(job #2054246)

Utilizator BLz0rDospra Cristian BLz0r Data 1 noiembrie 2017 20:07:57
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 3.79 kb
/*
*   Metoda Divide et Impera
*   Varianta 3, Problema 4
*
*   Autorul sursei: Dospra Cristian, grupa 235
*/
#include <fstream>
#include <cmath>
#include <iomanip>
#include <algorithm>
#include <vector>
using namespace std;

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

const long long INF = 1LL * 2e18;

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> puncte, middlePoints, aux;

/*
*   puncte: punctele date
*   middlePoints: punctele aflate la un momentdat la distanta < delta in stanga si dreapta liniei de separare
*   aux: auxiliar pentru interclasare
*/

//ordonez punctele crescator dupa ordonata
void customMerge(int st, int mid, int dr, int lineX, long long d) {

    int i = st, j = mid + 1;

    aux.clear();
    while (i <= mid && j <= dr) {

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

            if (1LL * lineX - puncte[i].x < d)
                middlePoints.push_back(puncte[i]);

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

            if (1LL * puncte[j].x - lineX < d)
                middlePoints.push_back(puncte[j]);

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

    while (i <= mid) {

        if (1LL * lineX - puncte[i].x < d)
                middlePoints.push_back(puncte[i]);

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

    while (j <= dr) {

        if (1LL * puncte[j].x - lineX < d)
            middlePoints.push_back(puncte[j]);

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

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

//solve divide et impera: la coborare punctele sunt sortate dupa abscisa, in urcare sunt sortate dupa ordonata
long long closestPoints(int st, int dr) {

    //daca am un singur punct nu pot da o distanta
    if (st >= dr) {
        return INF;
    }
    //daca am doua puncte (caz elementar) returnez distanta dintre ele
    if (st + 1 == dr) {
        //le ordonez dupa y
        if (puncte[st].y > puncte[dr].y)
            swap(puncte[st], puncte[dr]);

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

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

    //luam cea mai buna distanta din partea stanga si cea dreapta
    long long d1 = closestPoints(st, mid);
    long long d2 = closestPoints(mid + 1, dr);
    long long d = min(d1, d2);

    //sortam dupa ordonata si incercam sa vedem daca putem imbunatati folosind un punct din stanga respectiv unul din dreapta liniei de separare
    customMerge(st, mid, dr, puncte[mid].x, d);

    //pentru fiecare punct aflat la distanta maxim d de linia separatoare (pe abscisa)
    for (int i = 0; i < middlePoints.size(); ++i) {
        int go = min(i + 8, (int)middlePoints.size() - 1); //stiu ca pot exista maxim 7 puncte la distanta < d pe ordonata
        for (int j = i + 1; j <= go ; ++j) {
            d = min(d, dist(middlePoints[i], middlePoints[j])); //le verific
        }
    }
    middlePoints.clear();
    return d;
}

int main() {

    int n;

    //citire
    fin >> n;
    puncte.resize(n);

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

    //sortam dupa abscisa
    sort(puncte.begin(), puncte.end());

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

    return 0;
}