|
Given an array arr[][] consisting of pair of integers denoting coordinates. The task is to count the total number of rectangles that can be formed using given coordinates.
Examples:
Input: arr[][] = {{0, 0}, {0, 1}, {1, 0}, {1, 1}, {2, 0}, {2, 1}, {11, 11}}
Output: 3
Explanation: Following are the rectangles formed using given coordinates.
First Rectangle (0, 0), (0, 1), (1, 0), (1, 1)
Second Rectangle (0, 0), (0, 1), (2, 0), (2, 1)
Third Rectangle (1, 0), (1, 1), (2, 0), (2, 1)
Input: arr[][] = {{10, 0}, {0, 10}, {11, 11}, {0, 11}, {12, 10}}
Output: 0
Explanation: No Rectangles can be formed using these co-ordinates
Approach: This problem can be solved by using the property of the rectangle and Hash maps. If two coordinates of a rectangle are known then the other two remaining coordinates can be easily determined. For every pair of coordinates find the other two coordinates that can form a rectangle.
Below is the implementation of the above approach.
C++
#include <bits/stdc++.h>
using namespace std;
// Function to find number of possible rectangles with sides parallel to the coordinate axis
int countRectangles(vector<pair<int, int>>& ob) {
// Creating a set containing the points
set<pair<int, int>> points;
// Inserting the pairs in the set
for (int i = 0; i < ob.size(); ++i) {
points.insert(ob[i]);
}
int ans = 0;
for (int i = 0; i < ob.size(); ++i) {
for (int j = i + 1; j < ob.size(); ++j) {
// Check if points ob[i] and ob[j] form the diagonal of a rectangle
if (ob[i].first != ob[j].first && ob[i].second != ob[j].second) {
// Check if the other two corners of the rectangle are present in the set
if (points.count({ob[i].first, ob[j].second}) && points.count({ob[j].first, ob[i].second})) {
// Increase the answer
++ans;
}
}
}
}
// Return the final answer divided by 2, as each rectangle is counted twice
return ans / 2;
}
// Driver Code
int main() {
vector<pair<int, int>> ob = {{0, 0}, {1, 0}, {1, 1}, {0, 1}, {2, 0}, {2, 1}, {11, 23}};
cout << countRectangles(ob) << endl; // Output: 3
return 0;
}
import java.util.HashSet;
import java.util.Set;
public class RectangleCounter {
// Function to find number of possible rectangles with sides parallel to the coordinate axis
public static int countRectangles(int[][] points) {
// Creating a set to store the points for efficient lookup
Set<String> pointSet = new HashSet<>();
for (int[] point : points) {
pointSet.add(point[0] + "," + point[1]);
}
int ans = 0;
int n = points.length;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// Check if points points[i] and points[j] form the diagonal of a rectangle
if (points[i][0] != points[j][0] && points[i][1] != points[j][1]) {
// Check if the other two corners of the rectangle are present in the set
if (pointSet.contains(points[i][0] + "," + points[j][1]) &&
pointSet.contains(points[j][0] + "," + points[i][1])) {
// Increase the answer
ans++;
}
}
}
}
// Return the final answer divided by 2, as each rectangle is counted twice
return ans / 2;
}
// Driver Code
public static void main(String[] args) {
int[][] points = {{0, 0}, {1, 0}, {1, 1}, {0, 1}, {2, 0}, {2, 1}, {11, 23}};
System.out.println(countRectangles(points)); // Output: 3
}
}
def count_rectangles(points):
# Creating a set to store the points for efficient lookup
point_set = set(map(tuple, points))
ans = 0
n = len(points)
for i in range(n):
for j in range(i + 1, n):
# Check if points[i] and points[j] form the diagonal of a rectangle
if points[i][0] != points[j][0] and points[i][1] != points[j][1]:
# Check if the other two corners of the rectangle are present in the set
if (points[i][0], points[j][1]) in point_set and (points[j][0], points[i][1]) in point_set:
# Increase the answer
ans += 1
# Return the final answer divided by 2, as each rectangle is counted twice
return ans // 2
# Driver Code
points = [[0, 0], [1, 0], [1, 1], [0, 1], [2, 0], [2, 1], [11, 23]]
print(count_rectangles(points)) # Output: 3
using System;
using System.Collections.Generic;
public class RectangleCounter {
// Function to find number of possible rectangles with sides parallel to the coordinate axis
public static int CountRectangles(List<Tuple<int, int>> points) {
// Creating a set to store the points for efficient lookup
HashSet<Tuple<int, int>> pointSet = new HashSet<Tuple<int, int>>(points);
int ans = 0;
for (int i = 0; i < points.Count; i++) {
for (int j = i + 1; j < points.Count; j++) {
// Check if points[i] and points[j] form the diagonal of a rectangle
if (points[i].Item1 != points[j].Item1 && points[i].Item2 != points[j].Item2) {
// Check if the other two corners of the rectangle are present in the set
if (pointSet.Contains(Tuple.Create(points[i].Item1, points[j].Item2)) &&
pointSet.Contains(Tuple.Create(points[j].Item1, points[i].Item2))) {
// Increase the answer
ans++;
}
}
}
}
// Return the final answer divided by 2, as each rectangle is counted twice
return ans / 2;
}
// Driver Code
public static void Main() {
List<Tuple<int, int>> points = new List<Tuple<int, int>> {
Tuple.Create(0, 0), Tuple.Create(1, 0), Tuple.Create(1, 1), Tuple.Create(0, 1),
Tuple.Create(2, 0), Tuple.Create(2, 1), Tuple.Create(11, 23)
};
Console.WriteLine(CountRectangles(points)); // Output: 3
}
}
function countRectangles(points) {
// Creating a set to store the points for efficient lookup
const pointSet = new Set(points.map(point => point.toString()));
let ans = 0;
for (let i = 0; i < points.length; i++) {
for (let j = i + 1; j < points.length; j++) {
// Check if points[i] and points[j] form the diagonal of a rectangle
if (points[i][0] !== points[j][0] && points[i][1] !== points[j][1]) {
// Check if the other two corners of the rectangle are present in the set
if (pointSet.has([points[i][0], points[j][1]].toString()) &&
pointSet.has([points[j][0], points[i][1]].toString())) {
// Increase the answer
ans++;
}
}
}
}
// Return the final answer divided by 2, as each rectangle is counted twice
return ans / 2;
}
// Driver Code
const points = [[0, 0], [1, 0], [1, 1], [0, 1], [2, 0], [2, 1], [11, 23]];
console.log(countRectangles(points)); // Output: 3
Time Complexity: O(N2), Where N is the size of the array.
Auxiliary Space: O(N), Where N is the size of the array.
|
