Maximum number of overlapping rectangles with at least one common point | C ++ program for the above approach ; Function to find the maximum number of overlapping rectangles ; Stores the maximum count of overlapping rectangles ; Stores the X and Y coordinates ; Iterate over all pairs of Xs and Ys ; Store the count for the current X and Y ; Update the maximum count of rectangles ; Returns the total count ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; void maxOverlappingRectangles ( int x1 [ ] , int y1 [ ] , int x2 [ ] , int y2 [ ] , int N ) { int max_rectangles = 0 ; vector < int > X , Y ; for ( int i = 0 ; i < N ; i ++ ) { X . push_back ( x1 [ i ] ) ; X . push_back ( x2 [ i ] - 1 ) ; Y . push_back ( y1 [ i ] ) ; Y . push_back ( y2 [ i ] - 1 ) ; } for ( int i = 0 ; i < X . size ( ) ; i ++ ) { for ( int j = 0 ; j < Y . size ( ) ; j ++ ) { int cnt = 0 ; for ( int k = 0 ; k < N ; k ++ ) { if ( X [ i ] >= x1 [ k ] && X [ i ] + 1 <= x2 [ k ] && Y [ j ] >= y1 [ k ] && Y [ j ] + 1 <= y2 [ k ] ) { cnt ++ ; } } max_rectangles = max ( max_rectangles , cnt ) ; } } cout << max_rectangles ; } int main ( ) { int x1 [ ] = { 0 , 50 } ; int y1 [ ] = { 0 , 50 } ; int x2 [ ] = { 100 , 60 } ; int y2 [ ] = { 100 , 60 } ; int N = sizeof ( x1 ) / sizeof ( x1 [ 0 ] ) ; maxOverlappingRectangles ( x1 , y1 , x2 , y2 , N ) ; return 0 ; }