// timus 1369 kd-tree
// @author: Mircea Dima
//(c) Mircea Dima
// KD-TREES
// insert, sterge in complexitate O(logn)
// query O(sqrt(n))
#include <cstdio>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cassert>
#define eps 1e-14
#define N 100001
using namespace std;
struct point { double x, y; int id;point(){}; point(double a, double b){x=a;y=b;};};
struct cmp1
{
bool operator ()(const point &a, const point &b)const
{
if (a.x < b.x ) return 1;
return 0;
}
};
struct cmp2
{
bool operator ()(const point &a, const point &b)const
{
if (a.y < b.y ) return 1;
return 0;
}
};
int n,m;
vector<int> sol;
//#define distanta(a, b) ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y))
inline double distanta(point a, point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
struct nod
{
double x, y;
int id;
bool dir;
nod *l, *r;
nod (){};
nod (double _x, double _y, int _id, bool _dir, nod *_l, nod *_r)
{
x = _x;
y = _y;
id = _id;
dir = _dir;
l = _l;
r = _r;
};
};
// x,y coordonatele punctului dupa care se face taietura
// dir = directia ( 1 = coordonata X, 0 = coordonata Y)
// deleted = imi spune daca nodul l-am sters sau nu (pentru a face lazy deletion)
typedef nod* kd;
kd R,nil;
inline void init()
{
nil=new nod;
nil->l=nil->r=0;
nil->x=nil->y=0.0;
nil->dir=0;
//nil->deleted=0;
nil->id = 0;
R=nil;
}
inline void insert(kd &n, point P,bool dir, int id)
{
if(n == nil)
{
n=new nod;
n->l=n->r=nil;
n->x=P.x;
n->y=P.y;
n->dir=dir;
n->id = id;
return;
}
if(n->dir == 1)
{
if(P.x < n->x) insert(n->l, P,dir^1, id);
else insert(n->r, P,dir^1, id);
}
else
{
if(P.y < n->y) insert(n->l,P,dir^1, id);
else insert(n->r, P,dir^1, id);
}
}
//nearest neighbor O(sqrt(n))
int ids[4];
int nid;
double dist=0x3f3f3f3f;
inline void find_pos(kd &n, point P)
// caut dreptunghiul in care se afla punctul ...
{
if(n == nil) return;
//printf ("%lf_%lf\n", n->x, n->y);
if(n->dir == 1)
{
if(P.x < n->x) find_pos(n->l, P);
else find_pos(n->r, P);
}
else
{
if(P.y < n->y) find_pos(n->l, P);
else find_pos(n->r, P);
}
double d =distanta(P, point(n->x, n->y));
//if(n->deleted == 0)
bool ok = 1;
for (int i = 0; i < nid; ++i)
if (ids[i] == n->id)
ok = 0;
if (ok)
{
// printf ("___%lf %lf\n", d, dist);
if(dist > d)
{
dist=d;
sol.clear (),
sol.push_back (n->id);
// else if (fabs (dist - d) < eps)
// sol.push_back (n->id);
}
}
}
inline int intersect(double X0, double Y0, double X1, double Y1, point P, double R)
// verific daca dreptunghiul (X0, Y0, X1, Y1) se interesecteaza cu cercul de centru P si raza R
{
// if((P.x > X0 || fabs (P.x - X0) < eps) && (P.x < X1 || fabs (P.x - X1) < eps) &&
// (P.y > Y0 || fabs (P.y - Y0) < eps) && (P.y < Y1 || fabs (P.y - Y1) < eps)) return 1;
if(P.x + eps > X0 && P.x - eps < X1 && P.y + eps > Y0 && P.y - eps < Y1) return 1;
if(P.y + eps > Y0 && P.y - eps < Y1 && distanta(point(X0, P.y), P) - eps <R) return 1;
if(P.y + eps > Y0 && P.y - eps <Y1 && distanta(point(X1, P.y), P) - eps < R) return 1;
if(P.x + eps > X0 && P.x - eps <X1 && distanta(point(P.x, Y0), P) - eps < R) return 1;
if(P.x + eps > X0 && P.x - eps <X1 && distanta(point(P.x, Y1), P) - eps <R) return 1;
if(distanta(point(X0, Y0), P) - eps < R) return 1;
if(distanta(point(X1, Y0), P) - eps < R ) return 1;
if(distanta(point(X0, Y1), P) - eps < R ) return 1;
if(distanta(point(X1, Y1), P) - eps <R ) return 1;
return 0;
}
inline int intersect2(double X0, double Y0, double X1, double Y1, point P, double R)
// verific daca dreptunghiul (X0, Y0, X1, Y1) se interesecteaza cu cercul de centru P si raza R
{
// if((P.x > X0 || fabs (P.x - X0) < eps) && (P.x < X1 || fabs (P.x - X1) < eps) &&
// (P.y > Y0 || fabs (P.y - Y0) < eps) && (P.y < Y1 || fabs (P.y - Y1) < eps)) return 1;
if((P.x > X0 || fabs (P.x - X0) < eps) && (P.x < X1 || fabs (P.x - X1) < eps) &&
(P.y > Y0 || fabs (P.y - Y0) < eps) && (P.y < Y1 || fabs (P.y -Y1) < eps)) return 1;
if((P.y > Y0 || fabs (P.y - Y0) < eps) && (P.y < Y1 || fabs (P.y - Y1) < eps)
&& (distanta(point(X0, P.y), P) < R || fabs (distanta(point(X0, P.y), P) - R) < eps)) return 1;
if((P.y > Y0 || fabs (P.y - Y0) < eps) && (P.y < Y1 || fabs (P.y - Y1) < eps)
&& (distanta(point(X1, P.y), P) < R || fabs (distanta(point(X1, P.y), P) - R) < eps)) return 1;
if((P.x > X0 || fabs (P.x - X0) < eps) && (P.x < X1 || fabs (P.x - X1) < eps)
&& (distanta(point(P.x, Y0), P) < R || fabs (distanta (point (P.x, Y0), P) - R) < eps)) return 1;
if((P.x > X0 || fabs (P.x - X0) < eps) && (P.x < X1 || fabs (P.x - X1) < eps)
&& (distanta(point(P.x, Y1), P) < R || fabs (distanta (point (P.x, Y1), P) - R) < eps)) return 1;
if((distanta(point(X0, Y0), P) < R) ||
fabs (distanta (point (X0, Y0), P) - R) < eps)
return 1;
if(distanta(point(X1, Y0), P) < R ||
fabs (distanta (point (X1, Y0), P) - R) < eps) return 1;
if(distanta(point(X0, Y1), P) < R ||
fabs (distanta (point (X0, Y1), P) - R) < eps) return 1;
if(distanta(point(X1, Y1), P) < R ||
fabs (distanta (point (X1, Y1), P) - R) < eps) return 1;
return 0;
}
inline void query(kd n,point P, double X0, double Y0, double X1, double Y1)
// determina distanta pana la cel mai apropiat punct O(sqrt(n))
{
if(n == nil) return ;
// daca dreptunghiul nodului curent nu se intersecteaza cu cercul format de
// punctul P si de raza dist (cea mai mica distanta pana in momentul curent)
// nu mai verificam punctele din acest dreptunghi
if(intersect(X0, Y0, X1, Y1, P, dist) == 0 )return;//&& (rand () &1)) return;
//printf ("%lf %lf___\n", n->x, n->y);
double d=distanta(P, point(n->x, n->y));
// printf ("_%lf\n", d);
//if(n->deleted == 0)
bool ok = 1;
for (int i = 0; i < nid; ++i)
if (n->id == ids[i])
ok = 0;
if (ok)
{
// dist = dist;
//fprintf (stderr,"%lf\n", dist);
//printf ("%lf: %lf \n", d,dist);
if(dist > d)
dist=d,
sol.clear (),
sol.push_back (n->id);
else if (fabs (dist - d) < eps)
sol.push_back (n->id),
dist = d;
}
if( n->dir == 1)
{
query(n->l, P, X0, Y0,n->x, Y1);
query(n->r, P,n->x,Y0, X1, Y1);
}
else
{
query(n->l, P, X0, Y0, X1, n->y);
query(n->r ,P,X0, n->y, X1, Y1);
}
}
//end nearest neighbor
void ino (kd n)
{
if (n == nil) return;
ino (n->l);
printf ("%lf %lf %d\n", n->x, n->y, n->id);
ino (n->r);
}
point A[100001];
point B[10001];
int nA, nB;
kd build (kd &n, int l, int r, bool dir)
{
//printf ("_%d %d\n", l,r);
if (l >= r)
{
n = new nod;
n->dir = dir;
n->l = n->r = nil;
n->id = A[l].id;
n->x = A[l].x;
n->y = A[l].y;
return n;
}
if (dir)
sort (A + l, A + r + 1, cmp1());
else
sort (A + l, A + r + 1, cmp2());
int m = (r + l) / 2;
if (dir)
while (m > l && fabs (A[m].x - A[m-1].x) <eps) --m;
else
while (m > l && fabs (A[m].y - A[m-1].y) < eps) --m;
kd t = new nod;
t->dir = dir;
t->id = A[m].id;
t->x = A[m].x;
t->y = A[m].y;
t->l = l <= m - 1 ? build (t->l, l, m - 1 , dir ^1) : nil;
t->r = m + 1 <= r ? build (t->r, m + 1, r , dir ^1) : nil;
return t;
}
int main( )
{
srand (6626013);
init();
// freopen (args[1], "r", stdin);
freopen ("cmap.in","r",stdin);
freopen ("cmap.out", "w", stdout);
//scanf(" %d ", &nA);
int i;
int j;
int idd;
//for (i = 1; i <= nA; ++i)
scanf ("%d\n", &nA);
while (!feof (stdin))
{
++nA;
i = nA;
//cin >> idd >> A[i].x >> A[i].y;
scanf (" %lf %lf ",&A[i].x, &A[i].y);
A[i].id = idd;
}
R = build (R, 1, nA, 1);
//ino (R);
double Sol = 1e20;
double x0, y0;
for (i = 1; i <= nA; ++i)
{
nid = 0;
sol.clear ();
x0 = A[i].x;
y0 = A[i].y;
dist=1e20;//0x3f3f3f3f;
//printf ("_%lf\n", dist);
// printf ("%lf %lf\n", x0, y0);
ids[nid++] = A[i].id;
//printf ("%d ", A[i].id);
// for (int j = 0; j < nid; ++j)
// printf ("%d ", ids[j]);
// printf("\n");
find_pos(R, point(x0, y0));
//printf ("_%lf\n", dist);
// printf ("tacu\n");
query(R, point(x0, y0), -1000000001.0, -1000000001.0, 1000000001.0,1000000001.0);
assert (sol.size () != 0);
// printf ("%d\n", sol.size ());
if (Sol > dist)
Sol = dist;
}
printf ("%lf\n", Sol);
return 0;
}
Mircea Dima blasterz