In this article, we have discussed how to find the number of rectangles (parallel to the axes) possible from a given set of coordinate points.

Table of content:

1. Example
2. Brute Force Approach
3. Efficent Approach
4. Algorithm
5. Implementation
6. Complexity Analysis

Example

Let us suppose we have the set of coordinates as [{1,1}, {7,1}, {1,4}, {1,5}, {7,4}, {7,5}]

8 | 
7 | 
6 |  (1,5)             (7,5)
5 | *                 *
4 | *                 *
3 |  (1,4)             (7,4)
2 |  (1,1)             (7,1)
1 | *                 *
0 | _  _  _  _  _  _  _  _
    1  2  3  4  5  6  7  8
   

   
So, three rectangles can be formed from the given points.
*   (1,4)----(7,4)
     |         | 
     |         |    
    (1,1)----(7,1) 

*   (1,5)----(7,5)
     |         |
     |         |    
    (1,1)----(7,1) 

*   (1,5)----(7,5)
     |         |
     |         |    
    (1,4)----(7,4)
    

Brute Force Approach

Brute Force approach to the problem can be to select four coordinates point from the given set one by one and for each quadruplets find if a rectangle can be formed from it.
Selecting each Quadruplets would take O(n^4) time. So this is not an efficient method to solve this problem.

Efficient Approach

For a rectangle the diagonal end points can be (x1, y1) and (x2, y2) given that x1!=x2 and y1!=y2. This is because we are given that the rectangles should be parallel to axes. Also after we get two points as the diagonal end points, keeping the properties of rectangle in mind, the other two end points of the rectangle will be (x1, y2) and (x2, y1) .This is evident from the figure below.

(x1,y1)       (x2,y1) 
     *_ _ _ _*
     | \     |
     |  \    | 
     |   \   |
     |    \  |
     |     \ |
     |      \|
     *_ _ _ _*
(x1,y2)       (x2,y2)

So, the basic approach to solve this problem is that for every pair of points, say (x1, y1) and (x2, y2) we consider them to be the diagonal end points of some rectangle and check if there exist points (x1, y2) and (x2, y1) in the initial set so as to form a rectangle.

Algorithm

• Initialise a variable answer to store the number of possible rectangle. Let it initially be 0.
• Now we take two points at a time from the given set and check if they can form the end points of the diagonal of a rectangle that is if they are of the form (x1, y1) and (x2, y2) where x1!=x2 and y1!=y2.
• Now we check if the set contains the points (x1,y2) and (x2,y1) so as to form a rectangle (other two vertex of rectangle).
• If these two points exist in the set then it is possible to form a rectangle and thus we increment answer variable.

Let us understand this through an example.
Let us suppose we have the set of coordinates as [{1,1}, {7,1}, {1,4}, {1,5}, {7,4}, {7,5}]

Steps:

• answer=0

• taking points (1,1) and (7,1)
  they are not of the form (x1, y1) and (x2, y2) as y1=y2.
  Therefore they cannot form the endpoints of the diagonal.

• taking points (1,1) and (1,4)
  they are not of the form (x1, y1) and (x2, y2) as x1=x2.
  Therefore they cannot form the endpoints of the diagonal.

• taking points (1,1) and (1,5)
  they are not of the form (x1, y1) and (x2, y2) as x1=x2.
  Therefore they cannot form the endpoints of the diagonal.

• taking points (1,1) and (7,4)
  they are of the form (x1, y1) and (x2, y2)
  Therefore they can form the endpoints of the diagonal.
  Now checking if the other two vertex of the resulting rectangle are present in the set.
  The other two vertex are (x1,y2) and (x2,y1) i.e (1,4) and (7,1), both are present in the set therefore can form a rectangle.
  Thus incrementing answer.
  answer=1

• similarly checking for the other pairs we get total 3 rectangles possible.

Implementation:

#include <iostream>
#include<set>
using namespace std;
set<pair<int, int>> points;
int main() {
    int n;
    cin>>n;
    int a,b;
    for(int i=0;i<n;i++){
        cin>>a>>b;;
        points.insert(make_pair(a,b));
    }
    
    int answer = 0;
    
    for(auto i=points.begin(); i!=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;
             
        }
        
    }

    cout<<answer;

    return 0;
    
}

Complexity Analysis

Considering each pair of points as diagonal end points requires O(n^2) time.
And checking if the other two end points of the rectangle exist in the set using find function takes O(log n) time.
So the total time complexity is O(n^2 log n).

Also we do not require any extra space for computation, so the space complexity is constant.

So by the end of this article at OpenGenus, you must have a clear understanding of how to find the number of rectangles possible from a given set of coordinate points.