[백준] 2185 - 직사각형의 합집합 (c++)

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

IOI 1998 > Day 2 4번

 

문제 요약

직사각형 여러개가 입력으로 주어진다. 직사각형의 합집합의 둘레를 구해라

 

풀이 (Nlog(max_coord))

• 스위핑
• 세그먼트 트리

세그먼트 트리를 안 쓰고 N*(max_coord) 풀이도 충분히 돌아간다. 하지만 연습삼아 세그트리를 써서 시간복잡도가 좋은 풀이를 내봤다.

 

x축 y축 나눠서 스위핑을 한다고 생각해보자 둘레가 갱신되는 건 길이에 변화가 생기는 순간이란 관찰을 할 수 있다. 구간안에 전체 길이를 세그로 구하면 길이가 달라질 때, 달라진 만큼 답에 더해주면 된다. 중복을 제외하고 길이를 구하는 테크닉은 이 블로그에 자세히 나와있다.

https://ps.mjstudio.net/0-1-segment-tree

0-1 Segment Tree

 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mid (st+en>>1)
const int N =2e4+2;

int seg[4*N],cnt[4*N];
void update(int i,int st,int en,int l,int r,int a) {
    if(r<st||l>en)
        return;
    if(l<=st&&en<=r) 
        seg[i]+=a;
    else
        update(i*2,st,mid,l,r,a),update(i*2+1,mid+1,en,l,r,a);
    if(seg[i])
        cnt[i]=en-st+1;
    else if(st==en)
        cnt[i]=0;
    else
        cnt[i]=cnt[i*2]+cnt[i*2+1];
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n; cin>>n;
    vector<array<int,4>> v1,v2;
    for(int i=0,x1,y1,x2,y2;i<n;i++) 
        cin>>x1>>y1>>x2>>y2,
        v1.push_back({min(x1,x2),-1,y1,y2}),v1.push_back({max(x1,x2),1,y1,y2}),
        v2.push_back({min(y1,y2),-1,x1,x2}),v2.push_back({max(y1,y2),1,x1,x2});

    ll ans=0;
    auto f = [&](vector<array<int,4>> &v) {
        sort(v.begin(),v.end());
        int l=0;
        for(auto& [x,s,y1,y2]:v) {
            if(y1>y2)
                swap(y1,y2);
            y1+=N/2;y2+=N/2;
            update(1,1,N,y1,y2-1,-s);
            if(cnt[1]!=l)
                ans+=abs(cnt[1]-l);
            l=cnt[1];
        }
    };
    f(v1);
    fill(seg,seg+4*N,0); fill(cnt,cnt+4*N,0);
    f(v2);
    cout<< ans;
}