Find a line to cut two squares in half

Problem

Given two squares on a two-dimensional Cartesian plane, find a line that divides both squares into two equal halves. The line should pass through both squares such that each is split into two regions of equal area.

find-a-line-to-cut-two-squares-in-half-eg.excalidraw

Examples

Example 1

1
2
3


Input: a = Square(left=0, top=0, size=2), b = Square(left=2, top=0, size=2)
Output: Line passing through (1.0, 1.0) and (3.0, 1.0)
Explanation: The centers are (1,1) and (3,1). The line connecting these centers (y = 1) bisects both squares.

Example 2

1
2
3


Input: a = Square(left=0, top=0, size=2), b = Square(left=0, top=0, size=2)
Output: Any line through (1.0, 1.0) (centers coincide)
Explanation: Both squares have the same center (1,1). Any line through this center divides both squares equally; the implementation may return the center twice.

Solution

Method 1 – Center Line

Intuition

The only way to guarantee that a line divides both squares into two equal halves is for the line to pass through the center of each square. Any line passing through both centers will split both squares into two regions of equal area.

Approach

Compute the center point of each square.
The line connecting these two centers will cut both squares in half.
If the centers coincide, any line through the center will work.

Given the coordinates of the top-left corner and the size of each square, calculate the center for each. Return the line segment connecting the two centers.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


struct Point {
  double x;
  double y;
};

struct Square {
  double left;
  double top;
  double size;
  Point Center() const {
    return Point{left + size / 2.0, top + size / 2.0};
  }
};

std::pair<Point, Point> CutSquaresInHalf(const Square& a, const Square& b) {
  Point center_a = a.Center();
  Point center_b = b.Center();
  return {center_a, center_b};
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


type Point struct {
  X float64
  Y float64
}

type Square struct {
  Left, Top, Size float64
}

func (s Square) Center() Point {
  return Point{s.Left + s.Size/2, s.Top + s.Size/2}
}

func CutSquaresInHalf(a, b Square) (Point, Point) {
  return a.Center(), b.Center()
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


public class Point {
  public double x, y;
  public Point(double x, double y) {
    this.x = x;
    this.y = y;
  }
}

public class Square {
  public double left, top, size;
  public Square(double left, double top, double size) {
    this.left = left;
    this.top = top;
    this.size = size;
  }
  public Point center() {
    return new Point(left + size / 2.0, top + size / 2.0);
  }
}

public static Point[] cutSquaresInHalf(Square a, Square b) {
  return new Point[]{a.center(), b.center()};
}

1
2
3
4
5


data class Point(val x: Double, val y: Double)
data class Square(val left: Double, val top: Double, val size: Double) {
  fun center() = Point(left + size / 2.0, top + size / 2.0)
}
fun cutSquaresInHalf(a: Square, b: Square): Pair<Point, Point> = Pair(a.center(), b.center())

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


from dataclasses import dataclass
from typing import Tuple

@dataclass
class Point:
  x: float
  y: float

@dataclass
class Square:
  left: float
  top: float
  size: float

  def center(self) -> Point:
    return Point(self.left + self.size / 2, self.top + self.size / 2)

def cut_squares_in_half(a: Square, b: Square) -> Tuple[Point, Point]:
  return a.center(), b.center()

Complexity

⏰ Time complexity: O(1) — Only a constant number of arithmetic operations are performed to compute the centers and return the line.
🧺 Space complexity: O(1) — No extra space is used beyond a few variables for the centers and the result.

Problem#

Examples#

Solution#

Method 1 – Center Line#

Intuition#

Approach#

Code#

Complexity#