我一直在解決這個問題兩天，我能做的最好的是一個蠻力解決方案，它不夠高效。關於使用兩個矩形封閉點的算法謎題
給出一系列正座標點，範圍從(0, 0)到(1 billion, 1 billion)。您必須將所有點都包含在只有兩個具有儘可能小的總面積的矩形中。矩形必須具有與x軸和y軸平行的邊。矩形不能重疊，共享相同的邊界計數重疊。您**can**有0由0區域零的矩形。兩個矩形區域的總和爲**X**
您還必須找到一個包含所有點的最小可能區域的單個矩形。此區域爲**Y**
您正在努力尋找**Y** - **X**。
對於以下示例，答案**Y** - **X** = 107。
(4, 2), (8, 10), (1, 1), (9, 12), (14, 7), (2, 3)
提供代碼將非常讚賞，如果你這樣做，那麼請儘可能使用Java或C++。
我不想破壞遊戲。
從大矩形開始。然後你可以在每個x或y點上分割。
將點按x排序一次，每次y。
拆分垂直：
#######
#######
#######
#######
拆分horizonally：
##
## ####
####
####
分裂在座標產率兩組點的其中兩個矩形半部容易降低。
添加，因爲評論
由於Point類的解決方案，我實際使用int[2]所以X/Y可以作出選擇，作爲指數。另一方面，我必須創建一個AreaCollector類，其中一個簡單的Rectangle就足夠了。
我收集的矩形點也;沒有他們的代碼會變得更小。
static private class AreaCollector {
private final int[] lwb = new int[] { Integer.MAX_VALUE, Integer.MAX_VALUE };
private final int[] upb = new int[] { Integer.MIN_VALUE, Integer.MIN_VALUE };
public void add(int[] point) {
if (point[0] < lwb[0]) {
lwb[0] = point[0];
}
if (point[1] < lwb[1]) {
lwb[1] = point[1];
}
if (point[0] > upb[0]) {
upb[0] = point[0];
}
if (point[1] > upb[1]) {
upb[1] = point[1];
}
}
public int getArea() {
if (upb[0] == Integer.MIN_VALUE) { /// Zero points added.
return 0;
}
return (upb[0] - lwb[0]) * (upb[1] - lwb[1]);
}
}
public int solve(int[][] points) {
AreaCollector ac = new AreaCollector();
for (int[] point : points) {
ac.add(point);
}
final int y = ac.getArea();
final int n = points.length;
// Best solution sofar:
int[][] ascPoints = Arrays.copyOf(points, n);
int[][] descPoints = new int[0][];
int bestX = y + 0;
for (int direction = 0; direction < 2; ++direction) {
final int dir = direction;
Arrays.sort(points, Comparator.comparingInt((pt) -> pt[dir]));
int[] ascAreas = new int[n];
AreaCollector ascAC = new AreaCollector();
for (int i = 0; i < n;) {
int[] point = points[i];
int coord = point[direction];
for (int j = i; j < n && points[j][direction] == coord; ++j) {
ascAC.add(points[j]);
}
int area = ascAC.getArea();
for (int j = i; j < n && points[j][direction] == coord; ++j) {
ascAreas[j] = area;
++i;
}
}
int[] descAreas = new int[n];
AreaCollector descAC = new AreaCollector();
for (int i = n - 1; i >= 0;) {
int[] point = points[i];
int coord = point[direction];
for (int j = i; j >= 0 && points[j][direction] == coord; --j) {
descAC.add(points[j]);
}
int area = descAC.getArea();
for (int j = i; j >= 0 && points[j][direction] == coord; --j) {
descAreas[j] = area;
--i;
}
}
int bestI = -1;
for (int i = 0; i < n- 1; ++i) {
if (points[i][direction] != points[i + 1][direction]) {
int x = ascAreas[i] + descAreas[i + 1];
if (x < bestX) {
bestX = x;
bestI = i;
}
}
}
if (bestI != -1) {
ascPoints = Arrays.copyOfRange(points, 0, bestI + 1);
descPoints = Arrays.copyOfRange(points, bestI + 1, n);
}
}
return y -bestX;
}
作爲比較器，我使用了java 8簡潔表示法。如您所見，手工編碼部分的複雜性是O（N）代替Arrays.sort O（N.log N）。
好看又簡單。 –
其實想到如何實現這一點，並且有很少不平凡的問題，這可能是OP有問題的原因。仍然需要一些巧妙的查找策略來有效地計算實際面積（例如，通過將點集合作爲兩個排序後的集合 - 一個通過X軸，另一個通過Y並使用它們兩者）。 –
@PavelHoral是的，仍然需要一些智力。就我個人而言，我會以不同的方式做出來，做一個大綱路徑（外側的點），並試圖分裂它，需要更多的數據/算法智能。可能一個很好的解決方案是可行的。 –
以下是Java中的解決方案。計算完區域Y後，首先按X座標對座標進行排序，然後通過在每個X座標處將數組分割成兩半來計算矩形的面積（如果兩個座標具有相同的X值，則進行特殊處理）。然後它對Y座標也一樣。最小矩形區域是生成的X區域。
import java.util.Arrays;
import java.util.Comparator;
public class Puzzle {
public static void main(String[] args) {
int[][] COORDINATES_1 = { { 4, 2 }, { 8, 10 }, { 1, 1 }, { 9, 12 }, { 14, 7 }, { 2, 3 } };
int[][] COORDINATES_2 = { { 2, 1 }, { 2, 2 }, { 3, 1 }, { 3, 3 }, { 4, 3 }, { 5, 3 }, { 5, 4 }, { 6, 4 } };
int[][] COORDINATES_3 = { { 4, 2 } };
solve(COORDINATES_1);
solve(COORDINATES_2);
solve(COORDINATES_3);
}
public static void solve(int[][] coordinates) {
int size = coordinates.length;
int y = calcMinRectArea(coordinates, 0, size);
// sort by x coordinates
Arrays.sort(coordinates, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
int x = y;
for (int i = 1; i < size; i++) {
if (coordinates[i][0] == coordinates[i - 1][0])
continue; // several coordinates with the same x coordinates
x = Math.min(calcMinRectArea(coordinates, 0, i) + calcMinRectArea(coordinates, i, size - i), x);
}
// sort by y coordinates
Arrays.sort(coordinates, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[1] - o2[1];
}
});
for (int i = 1; i < size; i++) {
if (coordinates[i][1] == coordinates[i - 1][1])
continue; // several coordinates with the same y coordinates
x = Math.min(calcMinRectArea(coordinates, 0, i) + calcMinRectArea(coordinates, i, size - i), x);
}
System.out.printf("Y = %d, X = %d, Y - X = %d\n", y, x, y - x);
}
private static int calcMinRectArea(int[][] coords, int start, int length) {
if (length == 0)
return 0;
int minX = coords[start][0];
int maxX = minX;
int minY = coords[start][1];
int maxY = minY;
for (int i = start + 1; i < start + length; i++) {
int x = coords[i][0];
minX = Math.min(minX, x);
maxX = Math.max(maxX, x);
int y = coords[i][1];
minY = Math.min(minY, y);
maxY = Math.max(maxY, y);
}
return (maxX - minX) * (maxY - minY);
}
}
我希望看到人們瞭解這個難題。因爲我知道我不知道。也許你的例子的解決方案的圖表會解釋得更好一些。 –
你有一堆點。您可以使用總面積最小的兩個矩形來包圍所有點。這個地區是什麼？ 這足夠清楚了嗎？我不確定圖表如何幫助 –
查找解決方案給出「儘可能小的區域」可能是我在描述中缺少的。 –