Pagini recente » Cod sursa (job #1582552) | Cod sursa (job #870916) | Cod sursa (job #567638) | Istoria paginii runda/cerculetz_03/clasament | Cod sursa (job #1106719)
#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;
}