给出一个矩形R含有P点，正交轴，点是自然数。

Given a rectangle R containing P points, orthogonal with axes, points are natural numbers.

包裹是一个矩形，其中：

查找算法查找所有可能的包裹里面R，所以他们的总面积是最小的（最大化荒地面积）。

Find an algorithm to find all possible parcels inside R, so their total area is minimal (maximize wastelands area).

例：其中一个部门的许多方面，5点（*），2宗地

    R
|-----------------------------------------------|
|                   |                   |       |
|                   |                   |   *   |
|                   *                   |       |
|                   |                   *       |
|                   |               *   |       |
|                   |                   |       |
|                   |                   |       |
|                   |-----------*-------|       |
|    wastelands                         |       |
|                                       |       |
|                                       |       |
|-----------------------------------------------|

首先，让我们跳过优化（最大值/最小值）。有没有划分出一个矩形什么好办法？

Firstly, lets skip optimizing(max/min). Is there any good way to partition a rectangle?

这看起来可能是NP难的。我得到了这个问题的发起者和寻找所有可能的包裹是没有意义的一些反馈。 我认为唯一的办法就是使用一些启发式（如发现最大的包裹，包裹其中两侧含有最高分）和检查结果。

It looks like it might be NP-hard. I got some feedback from initiator of this problem and finding all possible parcels is pointless. I think the only way is to use some heuristic (e.g. finding biggest parcels or parcels which sides contain most of points) and check the results.

推荐答案

蛮力是要找到每个点包含点（内部）所有可能的矩形和解决的精确覆盖集问题的对集合中的所有矩形。

Brute force is to find for each point all possible rectangles that contain that point (in inside) and solve exact cover set problem on collection of all rectangles.

要查找包含给定的点所有的矩形是相对简单： - ）

To find all rectangles that contain given point is 'relatively' simple :-)

启动与具有最大一侧的矩形。例如。为点具有最大Y侧（A，B）的矩形是一个具有垂直边界上，其中x坐标点是最接近于（从两侧）和水平边界上R.如果有其他点即不区分（S ）与x坐标等于一，但将只能移动水平边界的最近点在y方向上。

Start with a rectangle that have maximal one side. E.g. for point (a,b) rectangle with maximal y side is one that has vertical boundaries on points which x coordinate is nearest to a (from both sides) and horizontal boundaries are on R. That is not case if there is other point(s) with x coordinate equal a, but that will only move horizontal boundary to the nearest point in y direction.

下一步矩形必须具有较小的Y侧，这意味着，用于垂直边界在较短的矩形边界点（B）用于水平边界。点的垂直边界是从同一侧点选择为B，支持矩形约束（创建矩形，在矩形区域没有其他一点。）

Next rectangle has to have smaller y side, that means that boundary point (B) that was used for vertical boundary in shorter rectangle is used for horizontal boundary. Point for vertical boundary is choose from point from same side as B to support rectangle constraints (create rectangle, no other point in rectangle area.)