※ 引述《FRAXIS (喔喔)》之铭言：
: 给定在平面上n个点的集合P及一正实数x，设计一线性算法判断x是否大于
: P中最靠近两点之距离。
: 我的解法无法满足algebraic decision tree model，不知道有没有办法
: 设计出一个满足algebraic decision tree model的算法。
: （只能用+-*/等代数运算和比较）
感觉很难达成线性时间...
我猜你的解法，应该是把平面切割成宽度为x的正方形网格
（上左边界是闭区间、下右边界是开区间）
一、不相邻的网格，距离一定超过x，没有检查的必要！
二、检查网格内部，若超过三个点，就一定有“距离小于x的点对”，算法结束
若不超过三个点，需要检查的点对，顶多3对，是常数
三、检查相邻八个网格：每个网格现在顶多三个点，需要检查的点对，顶多3*3*8对，常数
然而如何把每一个点归类于正确的网格呢？
这件事情本质上跟排序很相像
然而排序是 omega(nlogn)
所以我觉得很难达成线性时间