Pagini recente » Cod sursa (job #1727900) | Cod sursa (job #875027) | Cod sursa (job #2585162) | Cod sursa (job #1947087) | Cod sursa (job #749806)
Cod sursa(job #749806)
#include<fstream>
#include<algorithm>
#include<stdlib.h>
#include<math.h>
#define nmax 100005
#define inf 1000000
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 i, j , n, m, nr, t;
double D = inf;
int sizeA, sizeB;
inline double dist(Punct, Punct);
int bs(Punct b[], int sizeB, double x)
{
int step = 1 << 16, i;
for(i = 1; step ;step >>= 1)
if(i + step <= sizeB && b[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 int sp(int x)
{
return x*x;
}
inline double dist(Punct a, Punct b)
{
return sqrt((double)sp(abs(a.x- b.x)) + sp( abs( (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)
{
int m = (st + dr)/ 2;
if(dr <= st)
return inf;
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 << cmap( 1, n);
fin.close();
fout.close();
return 0;
}