钻井布局
(全国竞赛1999年B,D题)
勘探部门在某地区找矿。初步勘探时期已零散地在若干位置上钻井，取得了地质资料。进入系统勘探时期后，要在一个区域内按纵横等距的网格点来布置井位，进行“撒网式”全面钻探。由于钻一口井的费用很高，如果新设计的井位与原有井位重合（或相当接近），便可利用旧井的地质资料，不必打这口新井。因此，应该尽量利用旧井，少打新井，以节约钻探费用。比如钻一口新井的费用为500万元，利用旧井资料的费用为10万元，则利用一口旧井就节约费用490万元。
设平面上有 $n$ 个点 $P_i$，其坐标为 $(a_i,b_i),i=1,2,\cdots,n$，表示已有的 $n$ 个井位。新布置的井位是一个正方形网格 $N$ 的所有结点(所谓“正方形网格”是指每个格子都是正方形的网格；结点是指纵线和横线的交叉点)。假定每个格子的边长(井位的纵横间距)都是1单位(比如100米)。整个网格是可以在平面上任意移动的。若一个已知点 $P_i$ 与某个网格结点 $X_i$ 的距离不超过给定误差$\varepsilon$(=0.05单位)，则认为 $P_i$ 处的旧井资料可以利用，不必在结点 $X_i$ 处打新井。
为进行辅助决策，勘探部门要求我们研究如下问题：
- 假定网格的横向和纵向是固定的（比如东西向和南北向），并规定两点间的距离为其横向距离（横坐标之差绝对值）及纵向距离（纵坐标之差绝对值）的最大值。在平面上平行移动网格 $N$，使可利用的旧井数尽可能大。试提供数值计算方法，并对下面的数值例子用计算机进行计算。
- 在欧氏距离的误差意义下，考虑网格的横向和纵向不固定（可以旋转）的情形，给出算法及计算结果。
- 如果有 $n$ 口旧井，给出判定这些井均可利用的条件和算法（你可以任意选定一种距离）。
数值例子 $n=12$ 个点的坐标如下表所示：
| $i$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| $a_i$ | 0.50 | 1.41 | 3.00 | 3.37 | 3.40 | 4.72 | 4.72 | 5.43 | 7.57 | 8.38 | 8.98 | 9.50 |
| $b_i$ | 2.00 | 3.50 | 1.50 | 3.51 | 5.50 | 2.00 | 6.24 | 4.10 | 2.01 | 4.50 | 3.41 | 0.80 |