BOJ 7626. 직사각형

https://www.acmicpc.net/problem/7626

solved.ac: Platinum I (2024.09.10)

직사각형이 여러 개가 주어질 때 합집합의 넓이를 구하라는 문제다.

참 별 게 다 웰노운이다 싶다.

 

일단 x축 기준으로 쭉 정렬한 다음, 세로 선분들을 관리해주고 대충 스위핑질해주는 풀이이다.

 

세그먼트 트리 사용이 조금 특이하긴 하다.

 

두 가지 변수를 관리해주는데, 구간별 누적 길이랑 전체를 덮은 횟수를 기록해 준다.

전체를 덮은 횟수가 1 이상이라면 해당 구간의 값은 전체 길이와 동일하다.

그렇지 않다면 두 자식 노드로 쪼개고 그 합을 구하여 해결한다.

 

범위가 크니 좌표 압축을 해 주어야 한다.

딱히 쓸 게 없네요

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;
typedef long long int LL;

struct line
{
LL x;
LL y1, y2;
int val;

bool operator< (const line& l){return x < l.x;}
};

vector<line> lines;
vector<LL> comp;

LL tree[2000001], cnt[2000001];

void update(int node, int s, int e, int l, int r, int val)
{
  if(r < s || e < l) return;
  if(l <= s && e <= r) cnt[node] += val;
  else
  {
    int m = (s + e) / 2;
    update(node * 2, s, m, l, r, val);
    update(node * 2 + 1, m + 1, e, l, r, val);
  }

  if(cnt[node]) tree[node] = comp[e] - comp[s - 1];
  else
  {
    if(s == e) tree[node] = 0;
    else tree[node] = tree[node * 2] + tree[node * 2 + 1];
  }
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n;
  cin >> n;
  for(int i = 0; i < n; i++)
    {
      LL x1, x2, y1, y2;
      cin >> x1 >> x2 >> y1 >> y2;

      lines.push_back({x1, y1, y2, 1});
      lines.push_back({x2, y1, y2, -1});
      comp.push_back(y1);
      comp.push_back(y2);
    }

  sort(comp.begin(), comp.end());
  comp.erase(unique(comp.begin(), comp.end()), comp.end());

  sort(lines.begin(), lines.end());

  LL res = 0;
  line prv = lines[0];

  for(int i = 0; i < 2 * n; i++)
    {
      line cur = lines[i];
      LL dx = cur.x - prv.x;
      res += tree[1] * dx;

      LL s = lower_bound(comp.begin(), comp.end(), cur.y1) - comp.begin();
      LL e = lower_bound(comp.begin(), comp.end(), cur.y2) - comp.begin();
      update(1, 1, comp.size() + 1, s + 1, e, cur.val);
      prv = cur;
    }
  cout << res;
}