从给定的坐标集中找到矩形的数量

Question

我必须从给定的坐标集中找到最大的矩形数。

考虑以下在XY坐标系中给出的坐标3 10，3 8，3 6，3 4，3 0，6 0，6 4，6 8，6 10，

如何找到以下坐标是否形成矩形（3,0）（3,4）（6,4）（6,0）

运行时间限制：0.1秒

谢谢

Answer 1

对于每对点，例如 (x1, y1) 和 (x2, y2) 将其视为某个矩形的对角线。如果初始集合中存在点 (x1, y2) 和 (x2, y1)，那么我们就找到了我们的矩形。应该注意的是，将存在 2 条对角线代表相同的矩形，因此我们将最终答案除以 2。

这仅适用于平行于 x 轴或 y 轴的矩形。

伪代码 C++：

answer = 0;
set<pair<int, int>> points;

for(auto i=points.begin(); i!=std::prev(points.end()); i++)
{
    for(auto j=i+1; j!=points.end(); j++)
    {
        pair<int, int> p1 = *i;
        pair<int, int> p2 = *j;

        if(p1.first == p2.first || p1.second == p2.second)
            continue;

        pair<int, int> p3 = make_pair(p1.first, p2.second);
        pair<int, int> p4 = make_pair(p2.first, p1.second);

        if(points.find(p3) != points.end() && points.find(p4) != points.end())
            ++answer;
    }
}

return answer/2;

Answer 2

在“ y”坐标列表中按“ x”坐标分组，将点分开。在您的情况下，您将有两个排序列表：

3: [0,4,6,8,10]
6: [0,4,8,10]

做两个列表的交集，您会得到：[0,4,8,10]

其中任何两个将形成一个矩形：

[0,4] => (3,0), (3,4), (6,0), (6,4)
[0,8] => (3,0), (3,8), (6,0), (6,8)
[4,8] => (3,4), (3,8), (6,4), (6,8)
...

此解决方案仅适用于正交矩形，即其边平行于x，y轴。