Cod sursa(job #2245002)

Utilizator gabib97Gabriel Boroghina gabib97 Data 24 septembrie 2018 15:47:06
Problema Cele mai apropiate puncte din plan Scor 85
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <bits/stdc++.h>

#define N 100002

using namespace std;

struct point {
    long long x, y;
} P[N];

vector<int> median_points;

long long dist2(point a, point b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

long long find_min_dist(int a, int b) {
    int i, j;
    long long min_dist = LONG_LONG_MAX;

    if (b - a + 1 <= 3) {
        for (i = a; i <= b; i++)
            for (j = i + 1; j <= b; j++)
                min_dist = min(min_dist, dist2(P[i], P[j]));
    } else {
        // divide et impera
        int m = (a + b) >> 1;
        min_dist = min(find_min_dist(a, m), find_min_dist(m + 1, b));

        median_points.clear();
        for (i = a; i <= b; i++)
            if (abs(P[i].x - P[m].x) <= min_dist)
                median_points.push_back(i);
        sort(median_points.begin(), median_points.end(), [](int a, int b) -> bool { return P[a].y < P[b].y; });

        for (i = 0; i < median_points.size(); i++)
            for (j = 1; j <= 7; j++)
                if (i + j < median_points.size())
                    min_dist = min(min_dist, dist2(P[median_points[i]], P[median_points[i + j]]));
    }

    return min_dist;
}

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

    int n;
    fin >> n;
    for (int i = 1; i <= n; i++)
        fin >> P[i].x >> P[i].y;

    sort(P + 1, P + n + 1, [](const point &a, const point &b) -> bool { return a.x < b.x; });
    fout << fixed << setprecision(6) << sqrt((double) find_min_dist(1, n));

    return 0;
}