백준 9244 핀볼

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

 

선분끼리 서로 만나지 않는다는 조건 때문에 시작 위치가 결정되면 떨어지는 과정이 확정된다. 공이 떨어지는 과정을 시뮬레이션할 수 있을지 생각해보자. 선분은 일차함수의 조각이니 처음에는 리차오 트리를 쓰고 싶다는 생각이 들었다. 선분이 교차하지 않으니 공이 어떤 선분에 도달했을 때 하나의 x에서라도 도착한 선분보다 위에 있는 선분은 절대 탈 일이 없고, 이러한 위쪽 선분들은 다 지울 수 있다. 따라서 선분을 리차오에 잘 저장하고 원하는 선분을 잘 삭제할 수 있으면 풀 수 있겠다 싶었다. 

 

처음에는 리차오의 각 노드마다 set을 박아서 원하는 선분 삭제하기 같은 걸 생각했는데, set에 선분 NlogN개 삽입/삭제를 해야 하니 시간이 안 될 것 같았다. 결국 하고 싶은 건 선분을 logN개로 쪼개서 세그의 형태로 저장하는 것이고, 선분이 교차하지 않으니 선분의 상하관계가 바뀌는 일은 없다. 따라서 선분을 쪼개 담은 뒤, 노드마다 각 노드가 담당하는 x 범위에 들어가는 아무 x좌표를 골라 해당 점에서의 함수값 기준으로 선분을 정렬할 수 있다. 모든 노드에 대해 속한 선분을 정렬하면 f(x) >= y인 모든 선분 지우기 같은 연산을 해당 노드가 담고 있는 선분 중 가장 큰 거 몇 개 지우기 같은 식으로 처리할 수 있게 된다.

 

요약하면 아래 방법으로 문제를 풀 수 있다.

1. 세그먼트 트리의 방식으로 직선을 최대 logN개로 나누어 저장한다.

2. 세그트리의 각 노드에 저장된 직선을 함숫값 기준으로 정렬한다. 선분이 교차하지 않으니 어떤 x를 잡아도 정렬 결과는 동일하다.

3. 초기 좌표 (x0, inf)에서부터 다음 작업을 반복한다. 각 단계에서 현재 좌표를 (x, y)라고 두자.

3-1. x를 지나는 선분 중 x에서의 함숫값이 y 이상인 선분을 모두 지운다.

3-2. x를 지나고 x에서의 함숫값이 y 미만인 선분 중 가장 위에 있는 선분을 찾는다. 

3-3. (x, y)를 찾은 선분의 끝점으로 갱신하고, 찾은 선분보다 위에 있는 선분을 모두 지운다.

 

3-1, 3-2 과정은 x를 포함하는 logN개의 노드를 확인하여 수행할 수 있다. 3-3에서 위에 있는 선분을 모두 지우는 작업은 선분이 저장된 모든 노드에서 찾은 선분보다 정렬 순서가 뒤인 선분을 모두 지우는 식으로 할 수 있다. 어떤 선분을 지울 때, 해당 선분이 저장된 모든 노드를 다 보며 해당 선분보다 정렬 순서가 뒤인 선분을 연쇄적으로 지워주어야 할 것이다.

 

함숫값을 분수 형태로 관리했는데, 약분하는 과정이 시간을 많이 잡아먹어서 TLE를 받았다. 어차피 오버플로우는 안 나고, 약분을 굳이 하지 않으니 빠르게 풀 수 있었다. 그 밖에도 이것저것 자잘한 실수를 많이 했다. 요새 2000B 이상 짜면 무조건 디버깅으로 시간을 한참 잡아먹는 것 같은데.. 코드 설계를 구체적으로 안 하고 무지성코딩으로 들어가서 어쩔 수 없는 것 같다. 대회를 위해 코드 설계 연습이 필요하다고 생각한다.

 

사실 좀 뇌절을 많이 한 것 같다. https://leo630.tistory.com/143 에서 설명하는 스위핑 풀이가 훨씬 아름답고 깔끔하다고 생각한다. 

 

똑같이 Class 9인 Meteor Shower 문제도 비슷하게 풀릴 것 같은데,, 이건 좀 더 생각해봐야겠다.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
 
struct Line {
    ll x1, y1, x2, y2;
    pll get(int x) {
        return {y2*(x-x1) + y1*(x2-x), x2-x1};
    }
} L[101010];
vector<int> idxs[101010];
vector<int> seg[202020 << 2];
pii intv[202020 << 2];
pll tmp[101010];
int N, chk[101010];
 
// return a <= b
int cmp(pll a, pll b) {
    return a.first*b.second <= a.second*b.first;
}
 
void add(int now, int l, int r, int s, int e, int i) {
    if (r < s or e < l) return;
    if (s <= l and r <= e) {
        idxs[i].push_back(now);
        seg[now].push_back(i);
        return;
    }
    int m = l+r >> 1;
    add(now*2, l, m, s, e, i);
    add(now*2+1, m+1, r, s, e, i);
}
 
void dfs(int now, int l, int r){
    sort(seg[now].begin(), seg[now].end(), [&](int a, int b) {
        pll fa = L[a].get(l), fb = L[b].get(l);
        return fa.first*fb.second < fa.second*fb.first;
    });
    intv[now].first = l, intv[now].second = r;
    if (l == r) return;
    int m = l+r >> 1;
    dfs(now*2, l, m);
    dfs(now*2+1, m+1, r);
}
 
int main() {
    cin.tie(nullptr)->sync_with_stdio(0);
 
    cin >> N;
    vector<int> xc;
    for (int i = 1; i <= N; i++) {
        auto& [xs, ys, xe, ye] = L[i];
        cin >> xs >> ys >> xe >> ye;
        if (xs > xe) swap(xs, xe), swap(ys, ye);
        xc.push_back(xs);
        xc.push_back(xe);
    }
    ll x, y = 1e9;
    cin >> x;
    xc.push_back(x);
    sort(xc.begin(), xc.end());
    xc.erase(unique(xc.begin(), xc.end()), xc.end());
    for (int i = 1; i <= N; i++){
        L[i].x1 = lower_bound(xc.begin(), xc.end(), L[i].x1) - xc.begin() + 1;
        L[i].x2 = lower_bound(xc.begin(), xc.end(), L[i].x2) - xc.begin() + 1;
        add(1, 1, xc.size(), L[i].x1, L[i].x2, i);
    }
    dfs(1,1,xc.size());
    x = lower_bound(xc.begin(), xc.end(), x) - xc.begin() + 1;
    while (1) {
        int now = 1, l = 1, r = xc.size(), nxtL = 0;
        vector<int> q;
        now = 1, l = 1, r = xc.size();
        while (1) {
            while (seg[now].size()){
                int ni = seg[now].back();
                pll yy = L[ni].get(x);
                if (y*yy.second < yy.first) {
                    if (!chk[ni]) {
                        chk[ni] = 1;
                        q.push_back(ni);
                    }
                    seg[now].pop_back();
                }
                else {
                    if (!nxtL or cmp(L[nxtL].get(l), L[ni].get(l))) 
                        nxtL = ni;
                    break;
                }
            }
            if (l == r) break;
            int m = l+r >> 1;
            if (x <= m) now = now*2, r = m;
            else now = now*2+1, l = m+1;
        }
        if (!nxtL) break;
        if (!chk[nxtL]) {
            q.push_back(nxtL);
            chk[nxtL] = 1;
        }
        if (L[nxtL].y1 < L[nxtL].y2) x = L[nxtL].x1, y = L[nxtL].y1;
        else x = L[nxtL].x2, y = L[nxtL].y2;
        while (q.size()) {
            int i = q.back();
            q.pop_back();
            for (int segi : idxs[i]) {
                int nx = intv[segi].first;
                while (seg[segi].size() and cmp(L[i].get(nx), L[seg[segi].back()].get(nx))){
                    int li = seg[segi].back();
                    if (!chk[li]){
                        chk[li] = 1;
                        q.push_back(li);
                    }
                    seg[segi].pop_back();
                }
            }
        }
    }
    cout << xc[x-1];
}