Cod sursa(job #1324121)

Utilizator gabrielvGabriel Vanca gabrielv Data 21 ianuarie 2015 20:55:58
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.82 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);
 
    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(Q[i].first < S)
                X.push_back(make_pair(Q[i].second,Q[i].first));
 
        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(P[start].second > P[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());
 
    Q.resize(N);
 
    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;
}