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

http://poj.org/problem?id=2926 题意：给出n(1E5)个五维空间内的坐标...问最远的两个点距离多少。 思路：拆点即可。去绝对值。可以由二维空间推广到k维空间。一个点可以拆成2^(k-1)个点。 具体见代码。 /* *********************************************** Author :111qqz Created Time :2016年02月25日 星期四 00时19分46秒 File Name :code/poj/2926.cpp ************************************************ */ #include …

http://acm.split.hdu.edu.cn/showproblem.php?pid=5626 题意：给出n（1E6）个点的二维坐标，问距离最远的两个点的距离是多少。 思路：对曼哈顿距离进行变换。 先看曼哈顿距离的定义 |x1−x2|+|y1−y2| 拆绝对值 x1−x2+y1−y2或x1−x2+y2−y1 x2−x1+y1−y2或x2−x1+y2−y1 即|x1+y1−(x2+y2)|或|x1−y1−(x2−y2)| 设x1+y1为x′，x1−y1为y′ 则|x1′−x2′|或|y1′−y2′| 所以原要求1转化为 max(|x1′−x2′|,|y1′−y2′|)<=c …

http://www.lydsy.com/JudgeOnline/problem.php?id=1604 题意：了解奶牛们的人都知道，奶牛喜欢成群结队．观察约翰的N(1≤N≤100000)只奶牛，你会发现她们已经结成了几个“群”．每只奶牛在吃草的时候有一个独一无二的位置坐标Xi，Yi(l≤Xi，Yi≤[1．.10^9]；Xi，Yi∈整数．当满足下列两个条件之一，两只奶牛i和j是属于同一个群的： 1．两只奶牛的曼哈顿距离不超过C(1≤C≤10^9)，即lXi - xil+IYi - Yil≤C. 2．两只奶牛有共同的邻居．即，存在一只奶牛k，使i与k，j与k均同属一个群． 给出奶牛们的位置，请计算草原上有多少个牛群，以及最大的牛群里有 …