Cod sursa(job #2530092)

Utilizator irares27Rares Munteanu irares27 Data 24 ianuarie 2020 13:19:03
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.17 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 {
    long long x, y;
};

#define inf 99999999
#define vd vector<point>

long long get_dist_sqr(point a, point b) {
    return (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;
}

long long get_min_dist_sqr(point a, point b, point c) {
    long long d1 = get_dist_sqr(a, b);
    long long d2 = get_dist_sqr(b, c);
    long long d3 = get_dist_sqr(a, c);
    long long dm;
    dm = d1 < d2 ? d1 : d2;
    return d3 < dm ? d3 : dm;
}

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

long long distantaMinima(int st, int dr, vd &pointx, vd &pointy) {
 
   /* if (dr - st == 1) {
        return get_dist_sqr(pointx[st], pointx[dr]);
    }
    if (dr - st == 2) {
        return get_min_dist_sqr(pointx[st], pointx[st + 1], pointx[dr]);
    }*/

    if (dr - st <= 3) {
        long long dmin = get_dist_sqr(pointx[st], pointx[st + 1]);
        for (unsigned i = st; i < dr; i++)
            for (int j = i + 1; j <= dr; j++)
                if (get_dist_sqr(pointx[i], pointx[j]) < dmin)
                    dmin = get_dist_sqr(pointx[i], pointx[j]);
        return dmin;
    }

    else {
        int mij = (st + dr) / 2;
        point midPoint = pointx[mij];

        vd ord_st, ord_dr;
        for (unsigned i = 0; i < pointy.size(); i++) {
            if (pointy[i].x <= midPoint.x)
                ord_st.push_back(pointy[i]);
            else
                ord_dr.push_back(pointy[i]);
        }

        long long d1 = distantaMinima(st, mij, pointx, ord_st);
        long long d2 = distantaMinima(mij + 1, dr, pointx, ord_dr);
        long long dmin = d1 < d2 ? d1 : d2;

        vd fasie;
        for (unsigned i = 0; i < pointy.size(); i++) {
            if (pointy[i].x > midPoint.x - sqrt(dmin) and
                pointy[i].x < midPoint.x + sqrt(dmin))
                fasie.push_back(pointy[i]);
            /* if (abs(pointy[i].x - midPoint.x) < sqrt(dmin))
                 fasie.push_back(pointy[i]);*/
        }

        long long stripmin = get_min_strip(fasie);

        return stripmin < dmin ? stripmin : dmin;
        
    }
}

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);
    sort(pointy.begin(), pointy.end(), comparey);

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