论一类平面点对曼哈顿距离问题.ppt

《论一类平面点对曼哈顿距离问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一类平面点对曼哈顿距离问题的探究常州市第一中学陈子旸曼哈顿距离问题在信息学竞赛题目中十分常见曼哈顿距离的定义：在欧几里得空间的固定直角坐标系上两点所形成的线段对轴产生的投影的距离总和讨论将围绕一类平面上最大、最小曼哈顿距离点对问题展开目录引例情况一：离线查询、无修改情况二：在线查询、修改情况三：在线查询、无修改其他方法的讨论总结引例(magic)题目大意：在一个ｋ(k<=7)维的空间中，有ｎ(n<=100000)个点，要求求出在这些点对中曼哈顿距离最远的点对之间的曼哈顿距离。例题分析直接暴力枚举点对？显然TLE！两点间曼

2、哈顿距离的计算公式：以平面为例dist=

3、x1-x2

4、+

5、y1-y2

6、绝对值处理太麻烦！dist=

7、(x1-y1)-(x2-y2)

8、,(x1>x2&&y1>y2)

9、

10、(x1

11、(x1+y1)-(x2+y2)

12、,(x1>x2&&y1

13、

14、(x1y2)例题分析怎么处理？分类讨论？？？？ＮＯ！！！完全不需要！

15、x

16、+

17、y

18、>=

19、x+y

20、也就是说：如果我们计算时如果不满足条件，所计算出的值会比真实值小，不会更新答案！例题分析处理时，只需要分别统计

21、(x1+y1)-(x2+y2)

22、的最大值

23、和

24、(x1-y1)-(x2-y2)

25、的最大值，最后再取大的作答案就行了。高维推广处理方法类似，以三维为例，只要统计x+y+z,x+y-z,x-y+z,x-y-z四类情况的答案就可以了。通过引例，我们初步了解了这类问题的特点，同时发现了解决这类问题的一个重要的思想：去绝对值在引例中，运用了求最大值的条件和一个绝对值不等式，避免了分类讨论。但实际运用时往往要求最小值，我们不得不分类讨论解决这类问题，接下来的部分按题目的不同要求分析了几类不同情况。情况一：离线查询，无修改例题2(DONUT)题目大意：在一个平面上有两类点Ａ，Ｂ

26、。对于每个Ｂ类点求出离他曼哈顿距离最近的A类点与它的曼哈顿距离，其中Ａ类和Ｂ类点的个数都不超过50000个，点的坐标范围在长整数范围内。例题2分析能不能套用例题1（magic）的方法？dist=

27、(x1+y1)-(x2+y2)

28、,(x1>x2&&y1>y2)

29、

30、(x1

31、(x1-y1)-(x2-y2)

32、,(x1>x2&&y1

33、

34、(x1y2)糟糕！要求最小值

35、x

36、+

37、y

38、>=

39、x+y

40、例题2分析dist=

41、(x1+y1)-(x2+y2)

42、,(x1>x2&&y1>y2)

43、

44、(x1<

45、x2&&y1

46、(x1-y1)-(x2-y2)

47、,(x1>x2&&y1

48、

49、(x1y2)以分析在一个点左下的点为例例题2分析有点像二维RMQ问题？！树套树？二维ST？可以离线处理!例题2分析把所有点按照x的值排序，依次插入处理处理一个点时，所有插入的点的x的值都小于当前点，所以只需要满足y的条件就可以了处理对y的限制，只需要维护一棵维护x+y最大值的线段树，能够支持单点插入和区间查询最值两个操作就可以了情况二：在线查询、带修改例题3(DONUTEXT)在一个平面上给定一个点集，可以动态地插入或

50、删除点集中的点，并询问离点集中某个点最近的点到该点的曼哈顿距离。点集的大小不超过100000。例题3分析在线，带修改。离线算法神马的不管用了……我们需要一个能同时处理两个维度有序性的数据结构有没有想到区间第k大数问题？例题3分析在区间第k大数问题中，需要同时维护数在原序列中的位置和数的大小两个序关系在区间第k大数问题中，可以使用归并树这一结构下面来看一下如何把归并树运用到本题中例题3分析把x的值作第一关键字（类比区间第k大数问题中数在原数组的位置），y的值作第二关键字（类比区间第k大数问题中数的值），建立归并树所有x符合

51、查询要求的点分布在归并树中的O(log2n)个区间内，在每个区间中，y有序，可以通过二分答案找到y符合要求的区间。最后，只要把归并树的每个节点用线段树维护起来就可以了例题3分析123456781347256813472568134752681347256于是我们在O(nlog22n)的时间复杂度和O(nlog2n)的空间复杂度内解决了这个问题情况三：在线查询，无修改例题4(DONUTEXT2)题目大意：在一个平面上给定一个点集，查询距离点（x，y）最近的点离它的曼哈顿距离，这里的x，y由上两问的答案经过某种变化得到。例题

52、4分析从题面分析，这题似乎比上一题目要简单，因为没有修改操作若果直接套用上一题的做法，那这题就没有存在的意义了所以一定有效率更高的算法！如何超越nlog22n?我们想到了求解区间第k大数的又一神器划分树例题4分析直观地理解划分树，就是把快排的过程建成一棵树1347526813427568123456781234567