3453. Separate Squares I

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 of the squares above the line equals the total area of the squares below the line.

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

Note: Squares may overlap. Overlapping areas should be counted multiple times.

Math + Sorting

c++

class Solution {
public:
    double separateSquares(vector<vector<int>>& squares) {
        long double area = 0, sum = 0, py = 0, now = 0;
        for(auto& s : squares) area += s[2] / 2. * s[2];
        vector<pair<long long, long long>> S;
        unordered_map<long long, long long> mp;
        for(auto& s : squares) {
            mp[s[1]] += s[2];
            mp[s[1] + s[2]] -= s[2];
        }
        for(auto& [k,v] : mp) if(v) S.push_back({k,v});
        sort(begin(S), end(S));
        for(auto& [y, l] : S) {
            long double nxt = now + (y - py) * sum;
            if(nxt >= area) {
                return py + (area - now) / sum;
            }
            sum += l;
            now = nxt;
            py = y;
        }
        return -1;
    }
};

Binary Search

c++

class Solution {
    const long double EPS = 1e-9;
    long long helper(vector<vector<int>>& A, long double bar, long double area) {
        for(auto& a : A) {
            long double y = a[1], yy = a[1] + a[2];
            if(y >= bar) continue;
            area -= (min(yy,bar) - y) * a[2];
        }
        return area <= 0;
    }
public:
    double separateSquares(vector<vector<int>>& squares) {
        long double area = 0, l = 0, r = 2e9;
        for(auto& s : squares) area += 1ll * s[2] * s[2] / 2.;
        while(r - l > EPS) {
            long double m = l + (r - l) / 2;
            long long ok = helper(squares, m, area);
            if(ok) {
                r = m;
            } else l = m;
        }
        return l;
    }
};