BZOJ 2716: [Violet 3]天使玩偶 (动态kd-tree,带插入,曼哈顿距离模板题)

题目链接

Description

Input

Output

 

样例太长了,就不写了。

题意是说,现在有n个在二维平面,m个操作,2种类型,一种是加入一个点,另一种是对于一个定点,询问距离其最近的点的距离。

动态kd-tree的模板题,带插入操作。

插入其实就是直接暴力插的。

需要注意的是,这道题的距离度量是曼哈顿距离,略麻烦。

对于每个点,我们需要维护四个方向的极值。也就是kd-tree中某个节点所代表的空间,能管到的上下左右的最大(最小)坐标。

题解参考了iwtwiioi大爷的博客

代码风格参考了【bzoj 2716】[Violet 3]天使玩偶a  

 

 

 

 

poj 2926 Requirements (五维曼哈顿距离变换【拆点】)

http://poj.org/problem?id=2926
题意:给出n(1E5)个五维空间内的坐标…问最远的两个点距离多少。
思路:拆点即可。去绝对值。可以由二维空间推广到k维空间。一个点可以拆成2^(k-1)个点。 具体见代码。

hdu 5626 Clarke and points (曼哈顿距离变换,拆点)

http://acm.split.hdu.edu.cn/showproblem.php?pid=5626

题意:给出n(1E6)个点的二维坐标,问距离最远的两个点的距离是多少。

思路:对曼哈顿距离进行变换。

先看曼哈顿距离的定义

|x1x2|+|y1y2|

拆绝对值

x1x2+y1y2x1x2+y2y1

x2x1+y1y2x2x1+y2y1

|x1+y1(x2+y2)||x1y1(x2y2)|

x1+y1xx1y1y

|x1x2||y1y2|

所以原要求1转化为

max(|x1x2|,|y1y2|)<=c

然后分别对x,y排序即可..最大的距离一定是y[n-1]-y[0]或者x[n-1]-x[0]

 

 

bzoj 1604: [Usaco2008 Open]Cow Neighborhoods 奶牛的邻居 (曼哈顿距离的转化【拆点】+set+并查集)

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均同属一个群.
给出奶牛们的位置,请计算草原上有多少个牛群,以及最大的牛群里有多少奶牛

思路:一开始并没有什么思路…入手点是关于曼哈顿距离的转化。

先看曼哈顿距离的定义

|x1x2|+|y1y2|

拆绝对值

x1x2+y1y2x1x2+y2y1

x2x1+y1y2x2x1+y2y1

|x1+y1(x2+y2)||x1y1(x2y2)|

x1+y1xx1y1y

|x1x2||y1y2|

所以原要求1转化为

max(|x1x2|,|y1y2|)<=c

引用自:http://blog.csdn.net/wzq_QwQ/article/details/47746091

 

这样就有思路了。如果两个点属于同一个群,那么必须这两个点的x的差在c范围内,并且两个点的y的差也在范围内。 我们可以先按照一个 坐标排序,不妨以x为关键字排序,然后维护一段点的序列,使得这段序列中的所有的点的横坐标(其实就是最大减去最小)的差都在c范围内。然后对于序列中的所有点,我们想要知道有没有群“接纳”最新加入的点,二分找到比当前新加入点的纵坐标大的最小值和比当前新加入点的纵坐标小的最大值(set的lower_bound 第一次用),判断是否满足纵坐标的差在c的范围内。如果是,则用并差集合合并一下。

用multiset的原因是经过变换后点的坐标可能重复,以及multiset删除元素的时候不能直接删,因为会把所有相同的值删掉。

 

重要的话再说一遍:这道题最关键也是最大的收货就是,关于曼哈顿距离的变换。