Cod sursa(job #1106719)

Utilizator gabrielvGabriel Vanca gabrielv Data 13 februarie 2014 08:36:29
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 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;

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

    scanf("%d",&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(int i=start;i<=finish;i++)
            if(P[i].first < S)
                X.push_back(make_pair(P[i].second,P[i].first));

        sort(X.begin()+start, X.end()+finish+1);

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

        return S;
    }

    if(nr == 2)
    {
        return Abstand(P[start],P[finish]);
    }

    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;
}