Pagini recente » Cod sursa (job #56675) | Profil gosu_gamer | Cod sursa (job #1483742) | Cod sursa (job #936444) | Cod sursa (job #1689599)
#include<iostream>
#include<fstream>
#include<vector>
#include<cstdlib>
#include<queue>
#include<cmath>
#include<algorithm>
#include<iomanip>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
int const NMax = 100005;
long long const oo = 1LL*1<<60;
struct point{
long long x, y;
}P[NMax], Aux[NMax];
long long sol;
int n;
bool compareX(point a, point b)
{
return a.x < b.x;
}
bool compareY(point a, point b)
{
return a.y < b.y;
}
void Read()
{
int i;
f>>n;
for(i=1; i<=n; i++)
f>>P[i].x>>P[i].y;
sort(P + 1, P + n + 1, compareX);
}
long long dist(point a, point b)
{
return (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y);
}
long long DEI(int st, int dr)
{
if(st == dr)
return oo;
if(st == dr - 1)
return dist(P[st], P[dr]);
int mid = (st + dr)/2, k = 0, i, j;
long long a = DEI(st, mid);
long long b = DEI(mid+1, dr);
long long mini = min(a, b);
for(i=st; i<=dr; i++)
if(abs(P[i].x - P[mid].x) < mini)
Aux[++k] = P[i];
sort(Aux + 1, Aux + k + 1, compareY);
for(i = 1; i<=k; i++)
for(j = i+1; j<=k && j<=i+8; j++)
mini = min(mini, dist(Aux[i], Aux[j]));
return mini;
}
int main()
{
Read();
sol = DEI(1, n);
g<<fixed<<setprecision(6)<<sqrt(sol)<<"\n";
return 0;
}