Cod sursa(job #2076226)

Utilizator RendoRendoBoyz Rendo Data 26 noiembrie 2017 12:41:43
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <iomanip>

#define nMax 100000

using namespace std;

struct point {
    float x, y;
}v[nMax], ySorted[nMax];



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

bool compareX(point a, point b) {
    return a.x < b.x;
}

bool compareY(point a, point b) {
    return a.y < b.y;
}

double min(double a, double b) {
    return (a < b ? a : b);
}

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

double divide(int left, int right) {
    if (right - left == 1) {
        return dist(v[left], v[right]);
    }

    if (right - left == 2) {
        return min(dist(v[left], v[right]), min(dist(v[left], v[left + 1]),dist(v[left + 1], v[right])));
    }

    int m = (left + right) / 2;
    double leftDist = divide(left, m);
    double rightDist = divide(m + 1, right);
    double d = min(leftDist, rightDist);
    double delta = d;
    int k = 0;

    for (int i = left; i <= right; i++) {
        if (dist(v[i], v[m]) <= delta) {
            ySorted[k++] = v[i];
        }
    }

    sort(ySorted, ySorted + k, compareY);
    for (int i = 0; i < k - 1; i++) {
        for (int j = i + 1; j <= (i + 7) && j < k; j++) {
            d = min(d, dist(ySorted[i], ySorted[j]));
        }
    }

    return d;
}

int main() {
    int n;
    in >> n;
    for (int i = 0; i < n; i++) {
        in >> v[i].x >> v[i].y;
    }

    sort(v, v + n, compareX);
    double sol = divide(0, n-1);
    out << fixed << setprecision(6) << sol;
    return 0;
}