Cod sursa(job #1335078)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 4 februarie 2015 22:26:16
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.79 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>

#define Nmax 100100
#define oo (1 << 30)
#define distance(a, b) sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y))

using namespace std;

int N;
double Answer;
struct point {int x, y;} PointX[Nmax], PointY[Nmax], Tmp[Nmax];

bool compareX(point A, point B) {
    return A.x < B.x;
}
bool compareY(point A, point B) {
    return A.y < B.y;
}
double Dei(int left, int right) {

    if(left == right)
        return oo;
    else
    if(left + 1 == right) {
        if(PointY[left].y > PointY[right].y)
            swap(PointY[left], PointY[right]);

        return distance(PointX[left], PointX[right]);
    }

    int i, j, top, middle = (left + right) >> 1;
    double e = min(Dei(left, middle), Dei(middle + 1, right));

    merge(PointY + left, PointY + middle, PointY + middle + 1, PointY + right, Tmp, compareY);
    copy(Tmp, Tmp + (right - left), PointY + left);

    top = 0;
    for(i = left; i <= right; i++)
        if(abs(PointY[i].x - PointX[middle].x) < e)
            Tmp[++top] = PointY[i];

    for(i = 1; i < top; i++)
        for(j = i + 1; j - i <= 8 && j <= top; j++)
            e = min(e, distance(Tmp[i], Tmp[j]));

    return e;
}
void Solve() {

    sort(PointX + 1, PointX + N + 1, compareX);

    Answer = Dei(1, N);
}
void Read() {

    ifstream in("cmap.in");
    in >> N;

    for(int i = 1; i <= N; i++) {
        in >> PointX[i].x >> PointX[i].y;
        PointY[i].x = PointX[i].x;
        PointY[i].y = PointX[i].y;
    }

    in.close();
}
void Write() {

    ofstream out("cmap.out");
    out << fixed << setprecision(10) << Answer << '\n';
    out.close();
}
int main() {

    Read();
    Solve();
    Write();

    return 0;
}