Pagini recente » Cod sursa (job #156240) | Cod sursa (job #2352726) | Cod sursa (job #3123275) | Cod sursa (job #3227204) | Cod sursa (job #749811)
Cod sursa(job #749811)
#include <fstream>
#include <iostream>
#include <vector>
#include <cmath>
#include <cstdio>
#include<iomanip.h>
#include <algorithm>
#define nmax 100005
#define inf 3e10
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct Punct{
int x;int y;
inline void get()
{
fin >>x>>y;
}
inline void getout()
{
fout <<x <<" " << y <<'\n';
}
inline bool operator< (const Punct& P) const
{
return x < P.x || (x == P.x && y <P.y);
}
};
Punct v[nmax], dreapta[nmax], stanga[nmax];
int n;
int sizeA, sizeB;
inline double dist(Punct, Punct);
double min(double a, double b)
{
return a > b ? b : a;
}
int bs(Punct f[], int n, double x)
{
int step = 1 << 16, i;
for(i = 1; step ;step >>= 1)
if(i + step <= n && f[i + step].y <= x )
i += step;
return i;
}
inline bool cmp( const Punct& A,const Punct& B)
{
return A.y < B.y;
}
double join(Punct a[], Punct b[], double D)
{
int i, st, dr;
double rez = D;
sort(b + 1, b + 1 + sizeB,cmp);
for(i = 1; i <= sizeA; i++)
{
st = bs(b, sizeB, a[i].y -D);
dr = bs(b, sizeB, a[i].y +D);
for(int j = st; j <= dr; j++)
rez = min(rez,dist(a[i],b[j]));
}
//fout <<rez <<'\n';
return rez;
}
inline double sp(double x)
{
return x*x;
}
inline double dist(Punct A, Punct B)
{
return sqrt(sp(A.x- B.x) + sp( (A.y- B.y) ));
}
void read()
{
fin >> n;
for(int i = 1; i <= n ; ++i)
{
v[i].get();
}
//fout<<min(v[1].x, v[2].x);
sort( v + 1 , v + 1 + n );
}
double cmap(int st, int dr)
{
if(dr <= st)
return inf;
int m = (st + dr)>> 1;
double D = min( cmap(st, m), cmap(m + 1, dr) );
sizeA = sizeB = 0;
for(int i = st; i <= m;i++)
if(v[m].x - v[i].x < D)
stanga[++sizeA] = v[i];
for(int i = m + 1; i <= dr; ++i)
{
if(v[i].x - v[m].x < D )
dreapta[++sizeB] = v[i];
}
//fout << st << " " << dr << " " << D <<'\n';
if(!sizeA||!sizeB )
return D;
return join(stanga, dreapta, D);
}
int main()
{
read();
fout<< fixed;
fout << setprecision(6) << cmap( 1, n);
fin.close();
fout.close();
return 0;
}