Cod sursa(job #1335092)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 4 februarie 2015 23:05:10
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.95 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>

#define Nmax 100100
#define oo (1 << 30)

using namespace std;

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

inline double dist(point A, point B) {
    return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}
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 dist(PointX[left], PointX[right]);
    }

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

    i = left;
    j = middle + 1;
    for(top = left; top <= right; top++)
        if((PointY[i].y < PointY[j].y && i <= middle) || j > right)
            Tmp[top] = PointY[i++];
        else
            Tmp[top] = PointY[j++];

    for(i = left; i <= right; i++)
        PointY[i] = Tmp[i];

    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, dist(Tmp[i], Tmp[j]));

    return e;
}
void Solve() {

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

    for(int i = 1; i <= N; i++)
        PointY[i] = PointX[i];

    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;

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

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

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

    return 0;
}