如何找到在较小矩形的两侧留出最多自由空间的矩形

Question

我正试图为我的软件找出一个合适的算法，但我找不到任何相关的"教科书解决方案"；。我把任务归结为以下核心问题。

给定矩形区域的选择，我需要找到一个已知适合所有区域的较小矩形的所有边上同时留下最多空间的区域。

给定：矩形：长度=100，宽度=200

面积(总是预选为大于矩形(：

1. 长度=100，宽度=200
2. 长=101，宽=500
3. 长=101，宽=201
4. 长度＝300，宽度＝300<-这是最合适的，因为它同时在两个维度上都有最多的自由空间，尽管事实上还有其他选项有更多的空间，但只能在一个方向上
5. 长度=200，宽度=1000
6. 长=1000，宽=200

应该用什么算法来找到最适合的选择？

将感谢任何C语言或Python中的伪代码或代码，或指向某个著名算法的指针。

这些数字只是为这个测试示例选择的。在现实生活中，所有的数字都可以是用户输入的任何数字。

Answer 1

如果我正确理解你的问题，这将是一个解决方案(c++(，但没有测试它：

struct Rectangle
{
size_t x, y;
};
//returns first index which fits your condition
int alg(Rectangle a, Rectangle *others, size_t othersLen)
{
unsigned int biggestIndex = 0;
size_t biggest = 0;
for (int i = 0; i < othersLen; i++)
{
size_t diffX = others[i].x - a.x;
size_t diffY = others[i].y - a.y;
size_t size = diffX > diffY ? diffY : diffX;
if (size > biggest)
{
biggest = size;
biggestIndex = i;
}
}
return biggestIndex;
}

编辑：只有当其他矩形大于给定矩形时才有效，因为它不会产生负差异。