Find number of rectangles from a given set of coordinates

Question

I have to find max number of rectangles from a given set of coordinates.

Consider the following coordinates are given in an X Y coordinate system 3 10, 3 8, 3 6, 3 4, 3 0, 6 0, 6 4, 6 8, 6 10,

How can I find if the following coordinates form a rectangle (3,0) (3,4) (6,4) (6,0)

Running time constraint: 0.1 sec

Thank you

Answer 1

For every pair of points, say (x1, y1) and (x2, y2) consider it to be the diagonal of some rectangle. If there exist points (x1, y2) and (x2, y1) in the initial set then we have found our rectangle. It should be noted that there will exist 2 diagonals which will represent the same rectangle so we divide the final answer by 2.

This will work only for rectangles parallel to x-axis or y-axis.

PseudoCode 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;