Cod sursa(job #1541333)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 3 decembrie 2015 22:22:37
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.36 kb
#include <cstdio>
#include <cmath>
#include <algorithm>

#define x first
#define y second
using namespace std;

const int DIM = 100010;
const long long INF = 1000000000000000000LL;

pair <int, int> Points[DIM], Points2[DIM]; int nrPoints;

inline long long euclidianDistance (pair <int, int> point1, pair <int, int> point2) {
    return (point1.x - point2.x) * 1LL * (point1.x - point2.x) + (point1.y - point2.y) * 1LL * (point1.y - point2.y);
}

template <typename TYPE>
inline TYPE abs (TYPE X) {
    return X > 0 ? X : -X;
}

inline long long getDistance (int left, int right) {
    if (left != right) {
        int middle = left + (right - left) / 2;
        int distance = Points[middle].x;

        long long distance1 = getDistance (left, middle);
        long long distance2 = getDistance (middle + 1, right);
        long long distance3 = min (distance1, distance2);
        int index1 = left, index2 = middle + 1;
        int nrPoints2 = 0;

        while (index1 <= middle || index2 <= right) {
            if (index2 > right ) Points2[++nrPoints2] = Points[index1++]; else
            if (index1 > middle) Points2[++nrPoints2] = Points[index2++]; else
                if (Points[index1].y <= Points[index2].y)
                    Points2[++nrPoints2] = Points[index1++];
                else
                    Points2[++nrPoints2] = Points[index2++];
        }

        for (int index = left; index <= right; index ++)
            Points[index] = Points2[index - left + 1];
        nrPoints2 = 0;

        for (int index = left; index <= right; index ++)
            if (abs (Points[index].x - distance) <= distance3)
                Points2[++nrPoints2] = Points[index];

        for (int index1 = 1; index1 <= nrPoints2; index1 ++)
            for (int index2 = index1 + 1; index2 <= index1 + 7 && index2 <= nrPoints2; index2 ++)
                distance3 = min (distance3, euclidianDistance (Points2[index1], Points2[index2]));

        return distance3;
    } else
        return INF;
}

int main () {

    freopen ("cmap.in" ,"r", stdin );
    freopen ("cmap.out","w", stdout);

    scanf ("%d", &nrPoints);
    for (int i = 1; i <= nrPoints; i ++)
        scanf ("%d %d", &Points[i].x, &Points[i].y);

    sort (Points + 1, Points + nrPoints + 1);
    printf ("%.6f\n", sqrt(getDistance(1, nrPoints)));

    return 0;
}