Pagini recente » Cod sursa (job #1270910) | Cod sursa (job #2118801) | Cod sursa (job #1191992) | Cod sursa (job #960811) | Cod sursa (job #519190)
Cod sursa(job #519190)
#include<fstream>
#include<math.h>
#include<algorithm>
#include<iomanip>
#define inf "cmap.in"
#define outf "cmap.out"
#define NMax 101000
#define INF 100000000000000000LL
using namespace std;
fstream f(inf,ios::in),g(outf,ios::out);
struct punct { long long x,y; };
punct P[NMax];
int N;
void read()
{
punct p; long long x,y;
f>>N;
for(int i=1; i<=N; i++)
{
f>>x>>y; p.x=x; p.y=y;
P[i] = p;
}
}
inline long long min(long long a, long long b) { return ( a<b ? a : b ); }
inline long long p2(long long a) { return (a*a); }
inline long long dist(punct a, punct b) { return ( p2(a.x-b.x) + p2(a.y-b.y) ); }
long long dei(int st, int dr)
{
if( dr-st <= 2 )
{
if( st == dr+1 ) return dist(P[st], P[dr]);
long long r = INF;
for(int i=st; i<st+2; i++)
for(int j=i+1; j<=st+2; j++)
if( dist(P[i], P[j]) < r ) r = dist(P[i], P[j]);
return r;
}
int m, ls, ld;
long long d1, d2, d;
m = (st+dr)>>1;
d1 = dei(st, m); d2 = dei(m+1, dr);
d = min(d1, d2);
for(int i=m; i>=st; i--)
if( dist(P[m], P[i]) > d ) { ls = i+1; break; }
for(int i=m+1; i<=dr; i++)
if( dist(P[i], P[dr]) > d ) { ld = i-1; break; }
for(int i=ls; i<=m; i++)
for(int j=m+1; j<=ld; j++)
if( dist(P[i], P[j]) < d ) d = dist(P[i], P[j]);
return d;
}
struct cmp { bool operator () (const punct &a, const punct &b) { return (a.x<b.x); } };
void solve()
{
sort( P+1, P+N+1, cmp() );
g<< fixed << setprecision(6) << sqrt( dei(1,N) );
}
int main()
{
read(); solve();
f.close(); g.close();
return 0;
}