[LeetCode] 3454. Separate Squares II

https://leetcode.com/problems/separate-squares-ii/description/?envType=daily-question&envId=2026-01-14

LeetCode - Separate Squares II

문제 유형: 이진 탐색, 세그먼트 트리, 라인 스위핑

문제 난이도: Hard

 

문제

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.

 

2D정수배열 squares가 주어진다. squares[i] = [xi, yi, li]는 정사각형의 왼쪽 아래 꼭짓점의 주소와 한 변의 길이를 의미한다.

y=a꼴의 수평선을 그었을 때, 양쪽 넓이의 합을 균일하게 가르는 가장 작은 a를 구하시오.

10^-5의 오차를 허용한다.

겹치는 넓이도 단 한번만 계산한다.

 

풀이

editorial: https://leetcode.com/problems/separate-squares-ii/editorial

우선, 우리는 전체 넓이를 구해야 한다.

모양이 불규칙적이기에, 구간마다 나눠서 구해야한다.

특정 구간의 넓이를 구할 때, y좌표를 기준으로 구간을 나누면, 수평 너비에 대한 커버리지만을 따지면 된다.

수평 너비에 대해서는 세그먼트 트리로 따지면 된다.

 

세그먼트 트리의 내부는 다음과 같이 한다:

xs: x좌표 위치

count[pos] = 겹친 개수 추적

covered[pos] = 가로 축 전체 길이

 

그리고, 각 사각형 정보들을 다음의 이벤트들로 만든다:

(y, 1, x, x+l) ->  y부터 [x, x+l)구간 커버리지 1카운트 추가

(y+l, -1, x, x+l) -> y+l부터 [x, x+l)구간 커버리지 1카운트 제거

이 이벤트들을 y에 대해 오름차순정렬한다.

 

이 이벤트들을 파싱하여 세그먼트 트리를 초기화한 뒤,

순차적으로 읽으면서 구간의 직사각형 조각들의 합(수평 커버리지 * y구간 갭)을 누적한다.

그러면서 세그먼트 트리를 업데이트한다.

그러면서, 넓이와 그 누적합을 각 배열에 넣는다.

 

전체 넓이를 totalArea라고 하자.

우리가 원하는 것은:

(아래쪽 넓이) = (totalArea) / 2

이다.

 

어떤 y구간 [y_i, y_i+1]에 대해,

curArea < totalArea / 2이고,

curArea + width_i * (y_i+1 - y_i) >= totalArea / 2라면,

정답 y는 해당 구간 안에있다.

해당 구간 안에서는 가로 폭이 변하지 않으므로, 넓이는 선형적으로 증가한다.

 

구간 내에서 얼마나 더 올라가야하는지를 Δ라고 하면, 

curArea + width_i * Δ = totalArea / 2이다.

 

식을 정리하면, Δ = (totalArea/2 - curArea) / width_i이다.

 

즉, 해당 y구간을 먼저 구한다. lower_bound를 이용한 이진탐색을 누적합 배열에서 수행하고, -1을 해준다.

그 인덱스를 i라고 하자. i ~ i+1구간 사이에 있다.

구간에서의 Δ를 식대로 구해준 뒤, i까지의 높이를 더한 값이 정답이다.

 

 

코드

C++

using ll = long long;
class SegmentTree {
private:
    vector<int> count;
    vector<int> covered;
    vector<int> xs;
    int n;

    void modify(int qleft, int qright, int qval, int left, int right, int pos) {
        if(xs[right + 1] <= qleft || xs[left] >= qright) {
            return;
        }
        if(qleft <= xs[left] && xs[right + 1] <= qright) {
            count[pos] += qval;
        } else {
            int mid = (left + right) / 2;
            modify(qleft, qright, qval, left, mid, pos * 2 + 1);
            modify(qleft, qright, qval, mid+1, right, pos * 2 + 2);
        }

        if(count[pos] > 0) {
            covered[pos] = xs[right+1] - xs[left];
        } else {
            if(left == right) {
                covered[pos] = 0;
            } else {
                covered[pos] = covered[pos * 2 + 1] + covered[pos * 2 + 2];
            }
        }
    }

public:
    SegmentTree(vector<int>& xs_) : xs(xs_) {
        n = xs.size() - 1;
        count.resize(4 * n, 0);
        covered.resize(4 * n, 0);
    }

    void update(int qleft, int qright, int qval) {
        modify(qleft, qright, qval, 0, n-1, 0);
    }

    int query() { return covered[0]; }
};

class Solution {
public:
    double separateSquares(vector<vector<int>>& squares) {
        vector<array<int, 4>> events;
        set<int> xsSet;
        for(const auto &square : squares) {
            int x = square[0];
            int y = square[1];
            int l = square[2];
            int xr = square[0] + l;
            events.push_back({y, 1, x, xr});
            events.push_back({y + l, -1, x, xr});
            xsSet.insert(x);
            xsSet.insert(xr);
        }
        sort(events.begin(), events.end());
        vector<int> xs(xsSet.begin(), xsSet.end());

        SegmentTree seg(xs);

        vector<double> psum;
        vector<int> widths;
        double total_area = 0.0;
        int prev = events[0][0];

        for (auto &e : events) {
            int y = e[0];
            int delta = e[1];
            int xl = e[2];
            int xr = e[3];

            int len = seg.query();
            total_area += 1LL * len * (y - prev);
            seg.update(xl, xr, delta);

            psum.push_back(total_area);
            widths.push_back(seg.query());
            prev = y;
        }

        ll target = (ll)(total_area + 1) / 2;
        int i = lower_bound(psum.begin(), psum.end(), target) - psum.begin() - 1;
        double area = psum[i];
        int width = widths[i], height = events[i][0];

        return height + (total_area - area * 2) / (width * 2.0);
    }
};