Cod sursa(job #2530060)

Utilizator irares27Rares Munteanu irares27 Data 24 ianuarie 2020 12:45:30
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.28 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cmath>
using namespace std;

ifstream f("cmap.in");
ofstream g("cmap.out");

struct point {
    double x, y;
};

#define inf 99999999
#define vd vector<point>

double get_dist(point a, point b) {
    return sqrt((b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y));
}

bool comparex(point a, point b) {
    if (a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}

bool comparey(point a, point b) {
    if (a.y == b.y)
        return a.x < b.x;
    return a.y < b.y;
}

double get_min_dist(point a, point b, point c) {
    double d1 = get_dist(a, b);
    double d2 = get_dist(b, c);
    double d3 = get_dist(a, c);
    double dm;
    dm = d1 < d2 ? d1 : d2;
    return d3 < dm ? d3 : dm;
}

vd interclasare(vd a, vd b) {
    int n = a.size();
    int m = b.size();
    vd c(n + m);
    int i = 0, j = 0;
    int k = 0;
    while (i < n && j < m) {
        if (a[i].y < b[j].y) {
            c[k] = a[i];
            i++;
            k++;
        }
        else {
            c[k] = b[j];
            j++;
            k++;
        }
    }
    while (i < n) {
        c[k] = a[i];
        i++;
        k++;
    }
    while (j < m) {
        c[k] = b[j];
        j++;
        k++;
    }
    return c;
}

double get_min_strip(vd strip) {
    double min = inf;
    int n = strip.size();
    for (int i = 0; i <= n - 8; i++)
        for (int j = i + 1; j < i + 8; j++) {
            if (get_dist(strip[i], strip[j]) < min)
                min = get_dist(strip[i], strip[j]);
        }
    return min;
}

double distantaMinima(int st, int dr, vd pointx, vd pointy) {
 
    if (dr - st == 1) {
        if (pointy[st].y > pointy[dr].y)
            swap(pointy[st], pointy[dr]);
        return get_dist(pointx[st], pointx[dr]);
    }
    if (dr - st == 2) {
        sort(pointy.begin() + st, pointy.begin() + dr + 1, comparey);
        return get_min_dist(pointx[st], pointx[st + 1], pointx[dr]);
    }
    else {
        int mij = (st + dr) / 2;
        point midPoint = pointx[mij];

        double d1 = distantaMinima(st, mij, pointx, pointy);
        double d2 = distantaMinima(mij, dr, pointx, pointy);
        double dmin = d1 < d2 ? d1 : d2;

        vd Pyl;
        for (int i = st; i <= mij; i++)
            Pyl.push_back(pointy[i]);
        vd Pyr;
        for (int i = mij + 1; i <= dr; i++)
            Pyr.push_back(pointy[i]);

        vd Pyres = interclasare(Pyl, Pyr);
        vd strip;
        for (int i = st; i < dr - st + 1; i++) {
            if (abs(Pyres[i].x - midPoint.x) < dmin)
                strip.push_back(Pyres[i]);
        }

        float minstrip = get_min_strip(strip);

        return dmin < minstrip ? dmin : minstrip;
    }
}

int main()
{
    int n;
    f >> n;
    vd pointx(n), pointy(n);
    for (int i = 0; i < n; i++) {
        f >> pointx[i].x >> pointx[i].y;
        pointy[i] = pointx[i];
    }

    sort(pointx.begin(), pointx.end(), comparex);
    /*for (auto x : pointx)
        cout << x.x << " " << x.y << "\n";*/
    //sort(pointy.begin(), pointy.end(), comparey);

    g << std::setprecision(8) <<distantaMinima(0, n - 1, pointx, pointy);

    return 0;
}