Cod sursa(job #743777)

Utilizator mihai995mihai995 mihai995 Data 5 mai 2012 20:57:05
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.18 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 100005;
const double inf = 3e10;

int n, sizeA, sizeB;

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

struct Punct
{
    int x, y;

    inline void get()
    {
        in >> x >> y;
    }

    inline bool operator< (const Punct& P) const
    {
        return x < P.x || ( x == P.x && y < P.y );
    }
} v[N], stanga[N], dreapta[N];

inline bool cmp(const Punct& A, const Punct& B)
{
    return A.y < B.y;
}


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

inline double sq(double a)
{
    return a * a;
}

inline double dist(Punct A, Punct B)
{
    return sqrt(sq(A.x - B.x) + sq(A.y - B.y));
}

int bs(Punct v[], int n, double x)
{
    int i, step = 1 << 16;

    for (i = 1 ; step ; step >>= 1)
        if (i + step <= n && v[i + step].y <= x)
            i += step;

    return i;
}

double join(Punct a[], Punct b[], double D)
{
    int st, dr;

    sort(b + 1, b + sizeB + 1, cmp);

    for (int i = 1 ; i <= sizeA; i++)
    {
        st = bs(b, sizeB, a[i].y - D);
        dr = bs(b, sizeB, a[i].y + D);

        for (int j = st ; j <= dr ; j++)
            D = min(D, dist(a[i], b[j]));
    }

    return D;
}

double cmap(int st, int dr)
{
    if (dr <= st)
        return inf;

    int m = (st + dr) >> 1;

    double D = min(cmap(st, m), cmap(m + 1, dr));

    sizeA = sizeB = 0;

    for (int i = st ; i <= m ; i++)
        if (v[m].x - v[i].x < D)
            stanga[++sizeA] = v[i];

    for (int i = m + 1 ; i <= dr ; i++)
        if (v[i].x - v[m].x < D)
            dreapta[++sizeB] = v[i];
/*
    double sht = join(stanga, dreapta, D);

    cout << st << " " << dr << " " << sht << "\n";

    return sht;
*/
    if (!sizeA || !sizeB)
        return D;
    return join(stanga, dreapta, D);
}

int main()
{
    int n;

    in >> n;

    for (int i = 1 ; i <= n ; i++)
        v[i].get();

    sort(v + 1, v + n + 1);

    freopen("cmap.out", "w", stdout);

    printf("%.6lf\n", cmap(1, n));

    return 0;
}