1

Input : N rectangles. The coordinates for the rectangles are given.

Output : To check whether they form a square or not.

  • There can be overlapping among the rectangles.

I have solved for the case in which rectangles are parallel to the X and Y axis.

Soln :

Since the area of square is a perfect square ,so (Sum of area of total rectangles - Overlapping in between them ) should be a perfect square.

Now find the min. value of X coordinate of all the rectangles and max. value of Y coordinate. If they form a square then | min(x)-max(y) | is the length of the square. Now just find the sum of the area of the rectangles considering the overlaps. If it's equal to area of square with length | min(x)-max(y) |. Bingo !!

Complexity : O(n*n)

How to solve for general case ?

pseudo_teetotaler
  • 1,485
  • 1
  • 15
  • 35

3 Answers3

2

Assume that all rectangles form the square, but edges of rectangles are not parallel to axes.

Then the square has four vertices: top, bottom, right and left. The top vertex of the square has y-coordinate = max of y-coordinates of all vertices of all rectangles. So on for other three vertices: bottom (min y), right (max x), and left (min x).

To find the angle of the square it's sufficient only two vertices: bottom and right. Let's bottom vertex coordinates are (someX, minY), and right vertex coordinates are (maxX, someY). Then angle is atan((someY-minY)/(maxX-someX)). In C/C++/Java/C# you can use the function atan2.

After, rotate all rectangles on -angle, and then you can apply your algorithm for rectangles that are parallel for axes.

Mark Shevchenko
  • 7,937
  • 1
  • 25
  • 29
0

Mark's answer is correct if you already have an O(N^2) solution for the no-rotations case. However the toughest part of this problem is actually the inital no-rotations case (finding the total area of overlap to be exact).

I am not sure if you considered the case of multiple overlaps (more than 2 rectangles overlapping in one spot), but for those who are curious about finding the overlapping area:

There exists an interesting sweep algorithm that can be tuned to O(N log N) with use of some data structures.

Check this link if you are interested: Efficient algorithm to find Area of Overlapping Rectangles

Community
  • 1
  • 1
chris544
  • 889
  • 2
  • 10
  • 21
0

It is possible to do this in O(n). The sides of the rectangles that form part of the final square's sides will have smallest Y-intercept and the smallest X-intercept. You can use this to identify the sides that are part of the final boundary, by keeping track of the sides which make smallest X and Y intercepts.

Every side that that qualifies as the smallest intercept maker will be tested against the min/max value along the line and those values will be updated.

At the end, compare the min-max gap between the min-Y-intercept and min-X-intercept line segments and if they have the same length, then the final boundary is a square.

I can provide some pseudo-code if this is not clear. Let me know. I've added a figure to illustrate below: enter image description here

Arun R
  • 873
  • 6
  • 10