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

Question

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

考虑以下坐标在X Y坐标系中给出
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;
        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;