将矩形R的长为2d的边3等分，将它的长为d的边2等分，由此导出6个（d/2）×（2d/3）的矩形（如下图a所示）。若矩形R中有多于6个S中的点，则由鸽笼原理易知至少有一个（d/2）×（2d/3）的小矩形中有2个以上S中的点。设u，v是位于同一小矩形中的2个点，则：
distance（u，v）≤5d/6
（简答题）
在最接近点对问题中，用一条垂直线L：x=m将平面点集分为大致相等的两个子集S1和S2。设P1和P2分别表示直线L的左边和右边的宽为d的两个垂直长条区域，d1和d2分别是S1和S2中最小距离，且设d=min{d1，d2}。对于P1中任意一个点p，可能和在P2中点q构成全平面点集的最接近点对的候选点对，请证明：P2中最多有6对这样的候选点对。
正确答案
根据鸽笼原理：如果n+1只鸽子飞入n个笼子中，那么至少有一个笼子里包含两只或两只以上的鸽子。
将矩形R的长为2d的边3等分，将它的长为d的边2等分，由此导出6个（d/2）×（2d/3）的矩形（如下图a所示）。若矩形R中有多于6个S中的点，则由鸽笼原理易知至少有一个（d/2）×（2d/3）的小矩形中有2个以上S中的点。设u，v是位于同一小矩形中的2个点，则：
distance（u，v）≤5d/6
将矩形R的长为2d的边3等分，将它的长为d的边2等分，由此导出6个（d/2）×（2d/3）的矩形（如下图a所示）。若矩形R中有多于6个S中的点，则由鸽笼原理易知至少有一个（d/2）×（2d/3）的小矩形中有2个以上S中的点。设u，v是位于同一小矩形中的2个点，则：
distance（u，v）≤5d/6
答案解析
略
相似试题
（填空题）
X扫描线算法中，每次用一条扫描线进行填充，对一条扫描线填充的过程可分为4个步骤（）、（）、（）、（）。
（单选题）
用一条穿过圆的直线对一个圆执行修剪命令结果是：（）
（单选题）
下列哪一种格式画出了一条从（0，0）到（x，y）的直线（）.
（单选题）
用一条指令仅实现将AX←BX+SI的方法是（）。
（填空题）
用一条指令将寄存器AL的低4位取反，指令是（）。
（简答题）
试按要求编制程序段：用一条指令把CX中的整数转变为奇数（如原来已是奇数，则CX中数据不变，如原来是偶数，则（CX）+1形成奇数）。
（简答题）
用一条指令完成将AX的偶数位变反，奇数位不变的要求。
（简答题）
用一条指令完成将BX的高字节置‘1’，低字节不变的要求。
（简答题）
用一条指令完成将DX的高字节清零，低字节不变的要求。
