标签为 [KDtree] 的文章

BZOJ1941 Hide and Seek

题目传送门 Solution: 可能是我写KDtree最后一道题了,主要是重新理解了KDtree点到块的距离在针对最大值和最小值的不同计算方式。 结合前面的两篇: 1、插入 2、求最大(小)点对 3、求k远点对 也只会这些操作了,可能还是我太菜。 Code: C++ #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int n,m,ansmn,ansmx,opt,k1,k2,D,root,ans; struct node { int l,r,mn[2],mx[2],d[2]; }t[800010]; inline int read() { int ans=0, ......

BZOJ4520 K远点对

题目传送门 Solution: 一直想知道KDtree怎么求K远点对(可能是我比较菜),原来只是用一个堆来维护,其实也是一道模板题。 Code: C++ #include<cstdio> #include<algorithm> #include<cstring> #include<queue> #define ll long long using namespace std; priority_queue<ll,vector<ll>,greater<ll> > Q; int n,m,k1,k2,D,k,root; ll ans; struct node { int l,r; ll mn[2],mx[2],d[2]; }t[100010]; ll sqr(ll x) { return x*x; } inline ......

BZOJ2648 SJY摆棋子

题目传送门 开坑!!kdtree Solution: 先来简单的讲一下kdtree,是一个支持n维空间的插入和查询K远点对的数据结构,其本质就是经过优化的暴力搜索,至于建树过程(百度百科里介绍的很清楚),我们就以二维为例:平面内有(2,1),(3,2),(5,7),(6,4),(9,6)这些点,我们先按x坐标排序,然后取中间点为分割点,将整个二维平面以经过该点平行与y轴的直线一分为二,其中左边有(2,1),(3,2)两个点,我们再按y坐标排序,取中间点,再将左边平面以经过该点平行于x轴的直线一分为二,右边也是如此,递归下去,并记录每个节点 ......