在给定点集上找到与查询点最近的欧氏距离的做法当然是用经典的kd-tree解决啦~
但是需要注意,与kd-tree解决区域范围内查询不同,查询近邻时kd-tree的最坏复杂度一定是 $O(n)$ 的,只要第一个点集的分布范围不够友好(比如分成几个集中密集的点集,然后有的离得特别远),就可以在理论上被hack掉。之所以能过还是因为数据不卡+剪枝策略优秀。
const ll INF = 5141141919810114514ll;
// basic info and dimension
// use id when necessary
template <size_t K>
struct pt
{
int d[K], id;
pt<K>() = default;
};
template <size_t K>
struct point
{
pt<K> d, mx, mn; // current, max and min coordinate
int l, r; // lchild & rchild
ll v, sum; // weight & sum
point(pt<K> p = pt<K>(), ll _v = 0) { d = mx = mn = p, sum = v = _v; }
inline ll euclidean_dis(const point& o) const
{
ll ret = 0, dis = 0;
for (int i = 0; i < K; ++i)
{
dis = abs(d.d[i] - o.d.d[i]);
ret += 1ll * dis * dis;
}
return ret;
}
// use it only when o is outside
inline ll euclidean_dis_mn(const point& o) const
{
ll ret = 0, dis = 0;
for (int i = 0; i < K; ++i)
{
dis = 0;
if (o.d.d[i] < mn.d[i])
dis = mn.d[i] - o.d.d[i];
if (o.d.d[i] > mx.d[i])
dis = o.d.d[i] - mx.d[i];
ret += 1ll * dis * dis;
}
return ret;
}
inline ll euclidean_dis_mx(const point& o) const
{
ll ret = 0, dis = 0;
for (int i = 0; i < K; ++i)
{
dis = max(1ll * abs(mn.d[i] - o.d.d[i]), 1ll * abs(mx.d[i] - o.d.d[i]));
ret += 1ll * dis * dis;
}
return ret;
}
inline bool operator==(const point& a) const
{
for (int i = 0; i < K; ++i)
if (a.d.d[i] != this->d.d[i])
return false;
return true;
}
// all points from this sub-tree in this area
inline bool in(const point& Low, const point& Upp)
{
for (int i = 0; i < K; ++i)
if (!(this->mn.d[i] >= Low.d.d[i] && this->mx.d[i] <= Upp.d.d[i]))
return false;
return true;
}
// only it self in this area
inline const bool inself(const point& Low, const point& Upp) const
{
for (int i = 0; i < K; ++i)
if (!(this->d.d[i] >= Low.d.d[i] && this->d.d[i] <= Upp.d.d[i]))
return false;
return true;
}
// all points from this sub-tree are not in this area
inline const bool out(const point& Low, const point& Upp) const
{
for (int i = 0; i < K; ++i)
if (this->mn.d[i] > Upp.d.d[i] || this->mx.d[i] < Low.d.d[i])
return true;
return false;
}
};
template <size_t K>
struct KD_Tree_Static
{
// assume points[0] is default
vector<point<K> > points;
int root;
int n; // size of point
inline void print() const
{
for (int i = 1; i <= n; ++i)
printf("point %d : \n", i), points[i].print();
}
inline void update(int k)
{
int l = points[k].l, r = points[k].r;
for (int i = 0; i < K; ++i)
{
points[k].mn.d[i] = points[k].mx.d[i] = points[k].d.d[i];
if (l)
{
points[k].mn.d[i] = min(points[k].mn.d[i], points[l].mn.d[i]);
points[k].mx.d[i] = max(points[k].mx.d[i], points[l].mx.d[i]);
}
if (r)
{
points[k].mn.d[i] = min(points[k].mn.d[i], points[r].mn.d[i]);
points[k].mx.d[i] = max(points[k].mx.d[i], points[r].mx.d[i]);
}
}
points[k].sum = points[k].v + points[l].sum + points[r].sum;
}
// construct : return root
// cur_d : in 2D is bool, can be reconstructed to int
KD_Tree_Static() { points.clear(), points.push_back(point<K>()); }
// assume pts[0] is default
KD_Tree_Static(const vector<point<K> >& pts)
{
points.resize(pts.size());
n = pts.size() - 1;
vector<point<K>> tmp = pts;
function<int(int, int, int)> construct = [&](int l, int r, int cur_d)
{
if (l > r)
return 0;
int mi = (l + r) >> 1;
function<bool(const point<K>&, const point<K>&)> cmp = [&](const point<K>& a, const point<K>& b)
{
return a.d.d[cur_d] < b.d.d[cur_d];
};
nth_element(tmp.begin() + l, tmp.begin() + mi, tmp.begin() + r + 1, cmp);
points[mi] = tmp[mi];
int nxt = (cur_d == K - 1) ? 0 : cur_d + 1;
points[mi].l = construct(l, mi - 1, nxt); // use (cur_d + 1) % K when K > 2
points[mi].r = construct(mi + 1, r, nxt);
update(mi);
return mi;
};
root = construct(1, n, 0);
}
// query from subtree with root points[k]
inline ll _query(int k, const point<K>& lower, const point<K>& upper)
{
if (!k)
return 0;
ll ret = 0;
if (points[k].in(lower, upper))
return points[k].sum;
if (points[k].out(lower, upper))
return 0;
if (points[k].inself(lower, upper))
ret += points[k].v;
ret += _query(points[k].l, lower, upper) + _query(points[k].r, lower, upper);
return ret;
}
// query from [lower.d[0], upper.d[0]]x...x[lower.d[K-1], upper.d[K-1]]
ll query(const point<K>& lower, const point<K>& upper)
{
return _query(root, lower, upper);
}
// query distance
void _query_mn(ll& cur_min_dis, int k, const point<K>& a)
{
ll tmp_dis = points[k].euclidean_dis(a);
// if (!tmp_dis)
// tmp_dis = INF;
cur_min_dis = min(cur_min_dis, tmp_dis);
ll tmpl = points[k].l ? points[points[k].l].euclidean_dis_mn(a) : INF;
ll tmpr = points[k].r ? points[points[k].r].euclidean_dis_mn(a) : INF;
if (tmpl < tmpr)
{
if (tmpl < cur_min_dis)
_query_mn(cur_min_dis, points[k].l, a);
if (tmpr < cur_min_dis)
_query_mn(cur_min_dis, points[k].r, a);
}
else
{
if (tmpr < cur_min_dis)
_query_mn(cur_min_dis, points[k].r, a);
if (tmpl < cur_min_dis)
_query_mn(cur_min_dis, points[k].l, a);
}
}
ll query_min(const point<K>& a)
{
ll ret = INF;
_query_mn(ret, root, a);
return ret;
}
};
vector<point<2> > points;
point<2> low, upp;
signed main()
{
int T = rd();
while (T--)
{
int n = rd();
points.resize(n + 1);
for (int i = 1; i <= n; ++i)
{
points[i].d.d[0] = rd(), points[i].d.d[1] = rd(), points[i].d.id = i;
// points[i].v = rd();
}
KD_Tree_Static<2> kdt = KD_Tree_Static<2>(points);
ll ans = INF;
for (int i = 1; i <= n; ++i)
low.d.d[0] = rd(), low.d.d[1] = rd(), ans = min(ans, kdt.query_min(low));// wt(kdt.query_min(points[i]), '\n');
printf("%.3f\n", sqrt(ans));
}
return 0;
}