Cod sursa(job #919376)

Utilizator raulstoinStoin Raul raulstoin Data 19 martie 2013 17:00:17
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <fstream>
#include <vector>
#include<algorithm>
#include<cmath>
#include<iomanip>
#define oo 2000000000
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
vector < pair<int,int> > X,Y,V(100005);
int N;
void Read()
{
fin>>N;
for(int i = 1; i <= N; ++i)
    {
        int x,y;
        fin>>x>>y;
        X.push_back(make_pair(x,y));
    }
sort(X.begin(),X.end());
for(int i = 0; i < N; ++i)
{
    Y.push_back(make_pair(X[i].second,X[i].first));
}

}
int dist(pair<int,int> A,pair<int,int> B)
{
    return (B.first-A.first)*(B.first-A.first)+(B.second-A.second)*(B.second-A.second);
}

int Solve(int s,int d, vector < pair <int, int> >& X, vector < pair <int, int> >& Y)
{
if (s>=d-1)
{
    return oo;
}
if(s+2==d)
    {
        if(Y[s]>Y[s+1])
            swap(Y[s],Y[s+1]);
        return dist(Y[s],Y[s+1]);
    }
int m=(s+d)/2;
int best=min(Solve(s,m,X,Y),Solve(m,d,X,Y));
merge(Y.begin() + s, Y.begin() + m, Y.begin() + m, Y.begin() + d, V.begin());
copy(V.begin(), V.begin() + (d - s), Y.begin() + s);
int SIZE=0;
for(int i=s;i<d;i++)
    if(abs(Y[i].second-X[m].first)<=best)
        V[SIZE++]=Y[i];
for(size_t i=0;i<SIZE-1;i++)
    for(size_t j=i+1;j<SIZE&&j-i<8;j++)
        best=min(best,dist(V[i],V[j]));
return best;
}


int main()
{
    Read();
    fout<<fixed<<setprecision(6)<<sqrt(Solve(0,X.size(),X,Y));
    return 0;
}