Cod sursa(job #2494793)

Utilizator alecsanduSandu Alexandru Cristian alecsandu Data 18 noiembrie 2019 14:25:12
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.32 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <cfloat>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");
struct Point{
    double x, y;
};

int cmpX(const Point a, const Point b) {
    if(a.x != b.x)
        return (a.x < b.x);
    return (a.y < b.y);
}

int cmpY(const Point a, const Point b) {
    if(a.y != b.y)
        return (a.y < b.y);
    return (a.x < b.x);
}

double getdist(Point a, Point b) {
    return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}

double mindist3(Point v[], int n) {
    double min_d = DBL_MAX;
    for(int i = 0; i < n; ++i)//         try < n - 1 if shit happens
        for(int j = i + 1; j < n; ++j)
            if(min_d > getdist(v[i], v[j]))
                min_d = getdist(v[i], v[j]);
    return min_d;
}

double minInStrip(Point strip[], int n, double d) {
    double min_d = d;
    for(int i = 0; i < n; ++i)
        for(int j = i + 1; j < n && (strip[j].y - strip[i].y) < min_d; ++j)
            if(getdist(strip[i], strip[j]) < min_d)
                min_d = getdist(strip[i], strip[j]);
    return min_d;
}

double closestDistance(Point X[], Point Y[], int n) {
    if(n <= 3)
        return mindist3(X, n);
    int mid = n/2;
    Point midp = X[mid];
    Point Yleft[mid + 1], Yright[n - mid - 1];
    int li = 0, ri = 0;
    for(int i = 0; i < n; ++i) {
        if(Y[i].x < midp.x)
            Yleft[li++] = Y[i];
        else
            Yright[ri++] = Y[i];
    }

    double dleft = closestDistance(X, Yleft, mid);
    double dright = closestDistance(X + mid, Yright, n - mid);
    double d = min(dleft, dright);
    Point strip[n];
    int nr = 0;
    for(int i = 0; i < n; ++i)
        if(abs(Y[i].x - midp.x) < d)
            strip[nr++] = Y[i];
    return min(d, minInStrip(strip, nr, d));
}

double closestPair(Point v[], int n) {
    Point X[n], Y[n];
    for(int i = 0; i < n; ++i) {
        X[i] = v[i];
        Y[i] = v[i];
    }
    sort(X, X + n, cmpX);
    sort(Y, Y + n, cmpY);
    return closestDistance(X, Y, n);
}

int main() {
    int n;
    fin >> n;
    Point points[n];
    for(int i = 0; i < n; ++i) {
        double a, b;
        fin >> a >> b;
        points[i] = {a, b};
    }
    cout << closestPair(points, n);
    return 0;
}