Jan 13

LC-3453: Separate Squares I (Rust)

Each square contributes area based on how the line cuts through it
If line is at y = h and square has bottom at y, top at y + l:

Below: contributes min(h - y, l) of its height (clamped to [0, l])
Above: contributes max(y + l - h, 0) of its height


Since area = height × side_length, I can think in terms of "total height below" vs "total height above"

Approach:

* Total area of all squares = sum of l²
* I need: area_below = area_above = total_area / 2
* This is a monotonic function - as h increases, area below increases
* Use binary search on h


Example trace for [[0,0,1],[2,2,1]]:

Total area = 1 + 1 = 2, target = 1
At h = 1.0:

Square 1: height_below = min(1-0, 1) = 1 → area = 1×1 = 1
Square 2: height_below = min(1-2, 1) = 0 → area = 0×1 = 0
Total below = 1 ✓



Answer: 1.00000


```
impl Solution {
    pub fn separate_squares(squares: Vec<Vec<i32>>) -> f64 {
        // Calculate total area
        let total_area: f64 = squares.iter()
            .map(|sq| (sq[2] as i64 * sq[2] as i64) as f64)
            .sum();
        let target = total_area / 2.0;
        
        // Binary search bounds from actual data
        let mut lo = squares.iter()
            .map(|sq| sq[1] as f64)
            .min_by(|a, b| a.partial_cmp(b).unwrap())
            .unwrap();
        let mut hi = squares.iter()
            .map(|sq| (sq[1] + sq[2]) as f64)
            .max_by(|a, b| a.partial_cmp(b).unwrap())
            .unwrap();
        
        for _ in 0..100 {
            let mid = (lo + hi) / 2.0;
            let area_below = Self::area_below(&squares, mid);
            
            if area_below < target {
                lo = mid;
            } else {
                hi = mid;
            }
        }
        
        (lo + hi) / 2.0
    }
    
    fn area_below(squares: &Vec<Vec<i32>>, h: f64) -> f64 {
        squares.iter().map(|sq| {
            let y = sq[1] as f64;
            let l = sq[2] as f64;
            let height_below = (h - y).max(0.0).min(l);
            height_below * l
        }).sum()
    }
}
```