Description 这天，SJY显得无聊。在家自己玩。在一个棋盘上，有N个黑色棋子。他每次要么放到棋盘上一个黑色棋子，要么放上一个白色棋子，如果是白色棋子，他会找出距离这个白色棋子最近的黑色棋子。此处的距离是 曼哈顿距离 即(|x1-x2|+|y1-y2|) 。现在给出N<=500000个初始棋子。和M<=500000个操作。对于每个白色棋子，输出距离这个白色棋子最近的黑色棋子的距离。同一个格子可能有多个棋子。 Input 第一行两个数 N M 以后M行，每行3个数 t x y 如果t=1 那么放下一个黑色棋子 如果t=2 那么放下一个白色棋子 Output 对于每个T=2 输出一个最小距离 Sample Input …

题目链接 Description Input Output 样例太长了，就不写了。 题意是说，现在有n个在二维平面，m个操作，2种类型，一种是加入一个点，另一种是对于一个定点，询问距离其最近的点的距离。 动态kd-tree的模板题，带插入操作。 插入其实就是直接暴力插的。 需要注意的是，这道题的距离度量是曼哈顿距离，略麻烦。 对于每个点，我们需要维护四个方向的极值。也就是kd-tree中某个节点所代表的空间，能管到的上下左右的最大（最小）坐标。 题解参考了iwtwiioi大爷的博客 代码风格参考了【bzoj 2716】[Violet 3]天使玩偶a  /* …

题目链接 题意： 给出若干个点，在给出一个定点，求距离该定点最近的m个点。 思路： 我们已经知道kd-tree可以得到最近邻，实际上M近邻，只需要维护一个size为M的优先队列就可以了。 需要注意，优先队列的元素一定要先定义小于关系orz 以及这次采用了轮盘转的策略划分维度，也就是按照深度，所有维度轮流作为split-method（实际用起来效果还是挺棒的orz /* *********************************************** Author :111qqz Created Time :2017年10月08日 星期日 23时18分42秒 File Name :4347.cpp …

题目链接 题意： 有若干个(2E5)旅馆，分别给出旅馆的坐标和价格。有m个查询，每个查询给出一个人的位置(x0,y0),以及其能接受的最高价格。问在该人能接受的价格内，距离其最近的旅馆的坐标和价格是多少。 思路： kd-tree学习笔记 加了价格的限制其实无所谓，只要在更新的时候，先判一下价格就行了。 训练的时候不会kd-tree。。感觉有点可惜了。不然就6题了orz /* *********************************************** Author :111qqz Created Time :2017年10月08日 星期日 18时43分38秒 File Name :5992.cpp …

题目链接：hdu2966  题意： 给出二维平面上n(1E5)个点，问对于每个点，其他距离其最近的点的距离是多少。 思路： kd-tree 裸题。 kd-tree 学习笔记 /* *********************************************** Author :111qqz Created Time :2017年10月08日 星期日 18时43分38秒 File Name :2996.cpp ************************************************ */ #include <cstdio> #include <cstring> …

老规矩，资料先行。 好久没学新算法了，有点忘记怎么学了orz K-D tree 数据结构 hdu 2966 In case of failure　（k-d树　最近邻近点） 首先来看算法的提出。 现在二维平面上有n个点，知道这n个点的坐标，然后再添加一个点，问n个点中，距离新添加的点距离最近的点。 如果不做任何预处理，那么就是暴力枚举每个点，与该定点的距离。 如何优化呢？ 我们可以考虑把点域均等划分成若干个方块。 这样每次询问的时候只需要查询定点所在方格，以及定点相邻的8个方格中的点与该定点的距离即可。（除非这九个方格中没有点） 这种划分方法，对于随机数据大概是美滋滋，但是数据不会那么随机，因此划分也不能均等划 分。 这个时候， …