#3454

Separate Squares II

hard · 59.9% accepted · 272 likes · top 58%

array · binary search · segment tree · sweep line

⊣ practice⊣ open on leetcode ↗

Description

You are given a 2D integer array squares. Each squares[i] = [xi, yi, li] represents the coordinates of the bottom-left point and the side length of a square parallel to the x-axis.

Find the minimum y-coordinate value of a horizontal line such that the total area covered by squares above the line equals the total area covered by squares below the line.

Answers within 10-5 of the actual answer will be accepted.

Note: Squares may overlap. Overlapping areas should be counted only once in this version.

Solution