[BOJ 13329] Meteor Shower

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

 

팀연습에서 맞춘 문제 중 가장 어려운 문제가 아닐까 싶다. 정확히 말하면 맞추지는 못했고 풀이를 낸 이후에 코딩을 완성하지 못했다가, 조금만 손 보고 맞았다.

 

문제

y좌표가 모두 0보다 큰 영역에 대해, 컨벡스 헐이 $N$개 있다. $(0, 0)$에서 볼 수 없는 컨벡스 헐의 개수는?

 

풀이

우선 생각할 점은, 하나의 컨벡스 헐은 그 컨벡스 헐의 점 중 각도가 가장 큰 것과 작은 것의 선분으로 대체할 수 있다는 것이다. 문제에서 컨벡스 헐이 겹치지 않는다고도 했으니.. 아무튼 이 처리를 하고 나면 이 문제는 볼 수 없는 선분의 개수를 세는 문제로 바뀐다.

이 때 어떤 선분을 볼 수 없으려면, 그 선분이 커버하는 각도를 다른 선분들이 모두 커버해야 하며 그 선분보다 원점에 가까워야 한다. 즉 이 문제를 직선으로 펴서 생각하면, 상대적 상하관계가 주어지고 구간이 주어졌을 때 어떤 구간의 아래에 있는 구간이 해당 구간을 모두 커버하는지 판별하는 문제로 바뀌게 된다.

만약 상하관계를 적당히 $O(N)$개만 뽑아서 모든 선분의 상하관계를 정할 수 있다면, 나머지는 세그먼트 트리를 활용하여 쉽게 처리할 수 있다. 위상정렬을 하면서 구간에 색칠하고, 이미 모두 색칠되어있었다면 답에 1을 더하는 식으로 하면 되기 때문이다.

그렇다면 상하관계를 $O(N)$개만 뽑는 방법은 무엇일까? 이 것이 주된 고민거리였고, red1108과 함께 토론하며 알고리즘을 만들고 정당함을 확인했다. set에 각도 순서대로 점을 넣었다 빼며 현재 set에 들어있는 선분의 모든 쌍이 겹쳐있도록 관리한다. (이러한 상태이기 때문에, set에 넣을 자료형의 비교연산자로 두 선분이 어떠한 각도에서 겹쳐있음을 가정하고 상하관계를 비교할 수 있게 된다.) 이 때 새로 넣을 점이 선분의 시작 점이면, 선분을 추가한다. 이 때는 그냥 넣어주면 된다. 만약 새로 넣을 점이 선분의 끝 점이면, 선분을 제거한다. 이 때 제거하기 전에 set에서 위아래에 있던 선분을 확인하여 아래에서 현재 제거하려는 선분으로 가는 간선 하나, 현재 제거하려는 선분에서 위로 가는 간선 하나를 추가한다. 이렇게 할 경우 모든 구간의 상하관계의 위상을 알 수 있다.

 

이 알고리즘이 왜 되는지 생각해보자. 우선 구간이 겹치지 않는다면 처리 순서가 의미가 없으므로, A->B로 가던 B->A로 가던 상관이 없다. 때문에 구간이 겹치는 선분들에 대해서만 생각하면 된다. 만약 set에 A와 B가 들어가 있고, 순서상 A가 B보다 빠르다면 이는 A->B 길이 존재해야 함을 뜻한다. 이 때 원소를 빼면 항상 그 원소 이전 원소 -> 그 원소 ->그 원소 다음 원소꼴의 간선이 추가되기 때문에 임의의 인접한 두 원소에 대해 항상 간선이 생길 수밖에 없다. 때문에 위 알고리즘은 모든 위상학적 관계를 정확히 표현한다. 그리고 원소를 빼면서 간선이 최대 2개 추가되기 때문에 간선의 개수는 $O(N)$이다. 시간복잡도 또한 적절하다는 것을 알 수 있다.

또한 사이클은 생길 수 없다. 어떤 사이클이 존재하고, 사이클 시작점보다 끝점이 아래에 있다고 가정하고 이 사이클을 그림으로 그려 보면 중점의 위치관계가 언젠가는 왼쪽방향에서 오른쪽 방향으로(또는 반대로) 바뀌면서 끝점이 내려가야 하는데, 이 때 두 간선이 그렇게 만들어질 수 없다는 것을 깨달을 수 있다. a, b와 b, c가 겹치는 범위가 겹치므로 a와 c도 겹치고, a->c 간선도 존재한다. 하지만 c가 a보다 아래에 있어야 하는 상황이므로, 불가능하다.

 

위에서 설명한 방법으로 상하관계를 잘 정해주고 적절한 위상정렬과 세그먼트 트리를 사용하면 AC를 받을 수 있다. 다만 원래 풀이는 이보다 훨씬 간단한 것 같다. 그럼에도 불구하고 2차원 선분들의 위상적 상하관계를 정하는 빠른 알고리즘을 생각했기에 언젠가 유용하게 쓰이지 않을까 싶다. 그리고 찾다 보면 이 내용이 어느 논문에 있을 것 같기도 하다.

 

코드

#include <bits/stdc++.h>
#define eb emplace_back
#define em emplace
#define fi first
#define se second
#define all(v) v.begin(), v.end()

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int MAX = 101010;
const int INF = 1e9;
const ll LINF = 1e18;

ll ccw(pll a, pll b, pll c) {
    return (b.fi - a.fi) * (c.se - a.se) - (b.se - a.se) * (c.fi - a.fi);
}

struct Line {
    pll p1, p2;
    int idx;
    bool operator < (const Line T) const {
        if(ccw({0, 0}, p1, T.p1) > 0 && ccw({0, 0}, T.p1, p2) > 0) {
        	return ccw(p1, p2, T.p1) < 0;
        }
        else if(ccw({0, 0}, p1, T.p2) > 0 && ccw({0, 0}, T.p2, p2) > 0) {
        	return ccw(p1, p2, T.p2) < 0;
        }
        else return ccw(T.p1, T.p2, p1) > 0;
    }
};

Line line[MAX];
vector <int> g[MAX];
int in[MAX], L[MAX], R[MAX];

class SegmentTree {
    vector <bool> tree, lazy;
    int sz;
public:
    void Init(int n) {
        tree.resize(4*n+10);
        lazy.resize(4*n+10);
        sz = n;
    }
    void update_lazy(int node, int s, int e) {
        if(!lazy[node]) return;
        tree[node] = true;
        if(s != e) {
            lazy[node<<1] = lazy[node<<1|1] = true;
        }
        lazy[node] = false;
    }
    void update(int node, int s, int e, int l, int r) {
        update_lazy(node, s, e);
        if(s > r | e < l) return;
        if(s >= l && e <= r) {
            lazy[node] = true;
            update_lazy(node, s, e);
            return;
        }
        int m = (s + e) >> 1;
        update(node<<1, s, m, l, r);
        update(node<<1|1, m+1, e, l, r);
        tree[node] = tree[node<<1] && tree[node<<1|1];
    }
    void Update(int l, int r) {
        update(1, 1, sz, l, r);
    }
    
    bool cal(int node, int s, int e, int l, int r) {
        update_lazy(node, s, e);
        if(s > r || e < l) return true;
        if(s >= l && e <= r) return tree[node];
        int m = (s + e) >> 1;
        return cal(node<<1, s, m, l, r) && cal(node<<1|1, m+1, e, l, r);
    }
    bool Cal(int l, int r) {
        return cal(1, 1, sz, l, r);
    }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector <pair <pll, int> > pt;
    for(int i = 1; i <= n; i++) {
        int k;
        cin >> k;
        vector <pll> temp(k);
        for(int j = 0; j < k; j++) {
            cin >> temp[j].fi >> temp[j].se;
        }
        sort(all(temp), [](pll a, pll b) {
            return ccw({0, 0}, a, b) > 0;
        });
        pt.eb(temp[0], i);
        pt.eb(temp.back(), i);
        line[i].p1 = temp[0];
        line[i].p2 = temp.back();
        line[i].idx = i;
    }
    sort(all(pt), [](pair <pll, int> a, pair <pll, int> b) {
        return ccw({0, 0}, a.fi, b.fi) > 0;
    });
    set <Line> st;
    int cnt = 0;
    for(auto i : pt) {
        if(i.fi == line[i.se].p2) {
            auto it = st.find(line[i.se]);
            if(it != st.begin()) {
                g[prev(it)->idx].eb(it->idx);
                in[it->idx]++;
            }
            if(next(it) != st.end()) {
                g[it->idx].eb(next(it)->idx);
                in[next(it)->idx]++;
            }
            st.erase(it);
            R[i.se] = ++cnt;
        }
        else {
            st.em(line[i.se]);
            L[i.se] = ++cnt;
        }
    }
    
    queue <int> q;
    SegmentTree ST;
    for(int i = 1; i <= n; i++) {
        if(in[i] == 0) q.em(i);
    }
    ST.Init(4*n);
    int ans = 0;
    while(!q.empty()) {
        int x = q.front();
        q.pop();
        if(ST.Cal(2*L[x], 2*R[x])) ans++;
        ST.Update(2*L[x], 2*R[x]);
        for(auto i : g[x]) {
            in[i]--;
            if(in[i] == 0) q.em(i);
        }
    }
    cout << ans;
}