Finding the Balance: Solving the median Horizontal Line Problem

Link : https://leetcode.com/problems/separate-squares-i/

When working with computational geometry, we often face challenges involving area distribution. A classic example is finding a specific line that divides a set of shapes—in this case, squares—into two equal halves by area.

In this article, we’ll break down how to solve the Minimum Y-Coordinate for Equal Area problem using an efficient Binary Search approach in Rust.

---

The Problem Breakdown

We are given an array of squares, where each square is defined by its bottom-left coordinate (x_i, y_i) and its side length l_i. Our goal is to find a horizontal line y = L such that:

1. The total area of the squares below the line equals the total area of the squares above it.

2. If multiple lines satisfy this, we return the minimum y value.

Crucial Rule: Squares can overlap, and overlapping areas are counted multiple times. This simplifies things! It means we can treat each square independently rather than worrying about complex polygon unions.

---

Why Binary Search?

If we move a horizontal line from the very bottom (y_min) to the very top y_max, the area of the squares caught below that line is monotonically increasing.

Because the area function is monotonic (it never decreases as y increases), we can use Binary Search on the Answer. Instead of searching through an array, we are searching through a continuous range of possible y values.

---

The Strategy

1. Calculate Total Area: Sum up l_i^2 for all squares. Our target area for the below section is TotalArea / 2.

2. Define the Search Range:

   • low: The minimum y_i among all squares.

   • high: The maximum (y_i + l_i) among all squares.

3. The Precision Loop: Since we are dealing with floating-point numbers, we run the binary search for a fixed number of iterations (e.g., 100). This ensures high precision (well within the 10^{-5} requirement).

4. Area Calculation: For a given y = mid, calculate the area of each square that falls below it:

   • If mid is below the square, area = 0.

   • If mid is above the square, area = side^2.

   • If mid cuts through the square, area = (mid - y_start) x side.

---

The Implementation in Rust

Rust is perfect for this due to its performance and clear handling of numeric types.

Rust

impl Solution {
    pub fn find_median_y(squares: Vec<Vec<i32>>) -> f64 {
        let mut total_area: f64 = 0.0;
        let mut min_y = f64::MAX;
        let mut max_y = f64::MIN;

        // 1. Pre-calculate total area and global y-bounds
        for s in &squares {
            let y = s[1] as f64;
            let l = s[2] as f64;
            total_area += l * l;
            min_y = min_y.min(y);
            max_y = max_y.max(y + l);
        }

        let target = total_area / 2.0;
        let mut low = min_y;
        let mut high = max_y;

        // 2. Binary search for the y-coordinate
        // 100 iterations provides precision up to ~10^-30
        for _ in 0..100 {
            let mid = low + (high - low) / 2.0;
            if Self::calculate_area_below(&squares, mid) < target {
                low = mid;
            } else {
                high = mid;
            }
        }

        low
    }

    fn calculate_area_below(squares: &Vec<Vec<i32>>, line_y: f64) -> f64 {
        let mut current_area = 0.0;
        for s in squares {
            let y_start = s[1] as f64;
            let side = s[2] as f64;

            if line_y > y_start {
                // The height of the square portion below line_y
                let height_below = (line_y - y_start).min(side);
                current_area += height_below * side;
            }
        }
        current_area
    }
}

---