Pagini recente » Cod sursa (job #1804122) | Cod sursa (job #2444041) | Cod sursa (job #2886224) | Cod sursa (job #2793167) | Cod sursa (job #1324121)
#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;
}