Cod sursa(job #1106725)

Utilizator gabrielvGabriel Vanca gabrielv Data 13 februarie 2014 08:58:01
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.84 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define minim(a,b) ((a<b)?(a):(b))
#define oo 4e18
#define VP vector < pair < long long , long long > >

int N;

long long Sol;

VP P,Q;

void Scannen()
{
    freopen("cmap.in","r",stdin);

    scanf("%d",&N);

    Q.resize(N);

    for(int i=1;i<=N;i++)
    {
        long long x,y;
        scanf("%lld %lld",&x,&y);
        P.push_back(make_pair(x,y));
    }
}

inline long long Abstand(pair < long long, long long > a, pair < long long, long long > b)
{
    return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}

long long DEI(int start, int finish)
{
    int nr = finish-start+1;

    if(nr > 2)
    {
        long long S,S1,S2;
        int mij = (start + finish) / 2;
        S1 = DEI(start,mij);
        S2 = DEI(mij+1,finish);
        S = minim(S1,S2);

        VP X;

        for(unsigned i=start;i<= finish;i++)
            if(Q[i].first < S)
                X.push_back(make_pair(Q[i].second,Q[i].first));

        //sort(X.begin(), X.end());

        for(unsigned i=0; i < X.size(); i++)
            for(unsigned j=i+1; j < X.size() &&  j < i + 8 ; j++)
                S = minim(S,Abstand(X[i],X[j]));

        return S;
    }

    if(nr == 2)
    {
        Q[start] = P[start];
        Q[finish] = P[finish];
        if(Q[start].second > Q[finish].second)
            swap(Q[start],Q[finish]);

        return Abstand(P[start],P[finish]);
    }

    Q[start] = P[start];
    return oo;

}

void Losen()
{
    sort(P.begin(),P.end());

    Sol = DEI(0,N-1);
}

void Drucken()
{
    freopen("cmap.out","w",stdout);

    printf("%lf\n",sqrt(Sol * 1.0));
}

int main()
{
    Scannen();
    Losen();
    Drucken();

    return 0;
}