🟦 Separate Squares I

Difficulty: 🟡 Medium
Topics: Geometry, Binary Search, Prefix Area

📘 Problem Statement

You are given a 2D integer array squares.

Each square is represented as:

squares[i] = [xᵢ, yᵢ, lᵢ]

Where:

• (xᵢ, yᵢ) is the bottom-left coordinate
• lᵢ is the side length
• All squares are parallel to the x-axis

🎯 Objective

Find the minimum y-coordinate of a horizontal line such that:

🟥 Total area of squares above the line

🟦 Total area of squares below the line

📌 Important Notes

• Squares may overlap
• Overlapping areas are counted multiple times
• Answers within \(10^{-5}\) of the correct value are accepted

🧠 Key Insight

As you move the horizontal line upward:

• Area below the line increases
• Area above the line decreases

This creates a monotonic relationship, making the problem suitable for:

🔍 Binary Search on y-coordinate

🧪 Examples

✅ Example 1

Input

squares = [[0,0,1],[2,2,1]]

Output

1.00000

Explanation

Any horizontal line between y = 1 and y = 2 splits the total area evenly.
The minimum valid y is:

✔️ 1.00000

✅ Example 2

Input

squares = [[0,0,2],[1,1,1]]

Output

1.16667

Explanation

✔️ Areas above and below are equal at:

y = 7/6 ≈ 1.16667

📊 Constraints

🚀 Summary

• ✔️ Count partial square areas above & below a line
• ✔️ Overlaps are counted multiple times
• ✔️ Use binary search on y
• ✔️ Precision up to 1e-5

Happy Coding! 💻✨