Cod sursa(job #1644172)

Utilizator margikiMargeloiu Andrei margiki Data 9 martie 2016 21:50:51
Problema Cele mai apropiate puncte din plan Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
# include <bits/stdc++.h>
# define NR 100005
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
struct elem {
    double x, y;
}a[NR], aux[NR], var[NR];
bool cmp (elem x, elem y) {
    return x.x < y.x;
}
int i,j,n,m;

double dist (elem x, elem y) {
    return (x.x - y.x)*(x.x - y.x) + (x.y - y.y)*(x.y - y.y);
}
double divide (int ci, int cs) {
    if (cs-ci<=2) {
        double minn=INFINITY;
        for (int i=ci; i<=cs; ++i)
            for (int j=i+1; j<=cs; ++j)
                minn=min(minn, dist(a[i], a[j]));

        for (int i=ci; i<=cs; ++i) //sort cresc dupa Y
            for (int j=i+1; j<=cs; ++j)
                if (a[i].y < a[j].y) swap(a[i], a[j]);

        return minn;
    }

    int mij=(ci+cs)/2;
    double minn;
    double DR=a[mij].x;

    minn=divide (ci, mij);
    minn=min(minn, divide (mij+1, cs));

    int I=ci, J=mij+1, K=0, VV=0;
    while (I!=mij && J!=cs) {
        if (a[I].y > a[J].y) var[++K]=a[I++];
                        else var[++K]=a[J++];
    }
    while (I<=mij) var[++K]=a[I++];
    while (J<=cs)  var[++K]=a[J++];

    for (int i=ci; i<=cs; ++i)
        a[i]=var[i-ci+1];

    for (int i=ci; i<=cs; ++i)
        if (abs(a[i].x - DR) <= minn)
            var[++VV]=a[i];

    for (int i=1; i<=VV; ++i)
        for (int j=i+1; j<=i+7 && j<=VV; ++j)
            minn=min(minn, dist(var[i], var[j]));

    return minn;
}
int main ()
{
    f>>n;
    for (i=1; i<=n; ++i)
        f>>a[i].x>>a[i].y;
    sort (a+1, a+n+1, cmp);

    g<<fixed<<setprecision(7)<<sqrt(divide (1, n))<<"\n";

    return 0;
}