Skip to content

16.13. Bisect Squares

Description

Given two squares on a two-dimensional plane, find a line that would cut these two squares in half. Assume that the top and the bottom sides of the square run parallel to the x-axis.

Each square consists of three values, the coordinate of bottom left corner [X,Y] = [square[0],square[1]], and the side length of the square square[2]. The line will intersect to the two squares in four points. Return the coordinates of two intersection points [X1,Y1] and [X2,Y2] that the forming segment covers the other two intersection points in format of {X1,Y1,X2,Y2}. If X1 != X2, there should be X1 < X2, otherwise there should be Y1 <= Y2.

If there are more than one line that can cut these two squares in half, return the one that has biggest slope (slope of a line parallel to the y-axis is considered as infinity).

Example:


Input: 

square1 = {-1, -1, 2}

square2 = {0, -1, 2}

Output: {-1,0,2,0}

Explanation: y = 0 is the line that can cut these two squares in half.

Note:

  • square.length == 3
  • square[2] > 0

Solutions

Solution 1: Geometric Mathematics

We know that if a line can bisect two squares, then the line must pass through the centers of the two squares. Therefore, we can first calculate the centers of the two squares, denoted as $(x_1, y_1)$ and $(x_2, y_2)$, respectively.

If $x_1 = x_2$, then the line is perpendicular to the $x$-axis, and we only need to find the intersection point of the top and bottom edges of the two squares.

Otherwise, we can calculate the slope $k$ and the intercept $b$ of the line passing through the two centers, and then divide into two cases based on the absolute value of the slope:

  • When $|k| \gt 1$, the line passing through the two centers intersects with the top and bottom edges of the two squares. We calculate the maximum and minimum values of the vertical coordinates of the top and bottom edges, and then calculate the corresponding horizontal coordinate using the equation of the line, which is the intersection point of the two squares.
  • When $|k| \le 1$, the line passing through the two centers intersects with the left and right edges of the two squares. We calculate the maximum and minimum values of the horizontal coordinates of the left and right edges, and then calculate the corresponding vertical coordinate using the equation of the line, which is the intersection point of the two squares.

The time complexity is $O(1)$, and the space complexity is $O(1)$.

 1
 2
 3
 4
 5
 6