[Baekjoon - 16444] Contador de Pizza

난이도: Platinum III

 

태그

• Inversion Counting (Line Intersection Counting)
• Euler Characteristic (증명에 사용됩니다)

 

풀이

1. 만약 선이 교차하지 않는다면, 나눠지는 조각의 개수는?

선이 교차하지 않는다면, 위상수학적으로 볼 때 그냥 격자 모양이 됩니다.

즉, \( (N+1)(M+1) \)조각으로 나눠지겠죠.

2. [1]의 상태에서, 선을 하나 교차시켜보면?

한 쌍의 선이 교차되었고, 조건에 따라 이는 최대 1번 발생합니다.

그럼, 이 교차점이 속하지 않는 면은 무시하고, 교차점이 속하는 면만 봅시다.

 

위 그림과 같이, 3개였던 면이 4개로 변하는 걸 볼 수 있습니다.

 

추가로, [1]의 상태에서 교차시킨다고 하지만, 조금만 생각해보면 사실 [1]의 상태가 아니어도 교차를 하나 추가할 때마다 면이 하나가 추가되는 걸 볼 수 있으며,

[1]에서 출발해서 적당한 양의 교차를 시키면 원하는 상태로 도달하는 걸 알 수 있습니다.

 

직선의 교차 횟수는 Inversion Counting으로 풀어주면 되며, 문제의 답은 \( (N+1)(M+1) \) + Inversion의 수 가 됩니다.

 

Additional. 엄밀한 증명

오일러 공식 \( v - e + f = \chi \)를 사용합니다.

 

문제의 조건에 맞게 평면 그래프를 하나 만들어보면, 4개의 변수는 아래와 같이 계산할 수 있습니다.

• 정점의 개수 \( v \): 두 선이 교차하는 위치
  이 경우는 가로선의 개수 \( n+2 \) × 세로선의 개수 \( m+2 \) + 같은 방향의 선끼리 교차 횟수 \( i \)가 되겠죠.
• 간선의 개수 \( e \): (교차가 없는) 선의 개수
  하나의 선은, 이와 교차하는 선의 개수 + 1조각으로 나눠집니다.
  가로선만 두고 생각해보면, 하나의 가로선은 \( m \)개의 세로선과 교차되는 가로선들에 영향을 받겠죠.
  // 왜 \( m+2 \)가 아니라 \( m \)이냐면, 2번 발생하는 끝점에서의 교차는 선을 나누지 않기 때문입니다.
  이를 토대로 식을 세우면, \( (n+1)(m+2) + (m+1)(n+2) + 2i \)가 됩니다.
  // 여긴 왜 \( 2i \)냐면, 교차할 때마다 2개의 선이 4개의 선으로 나눠지기 때문입니다.
• 면의 개수 \( f \): 답과 관련있는 값
  엄밀히는, 문제의 답을 \( a \)라 할 때 \( f = a+1 \)이 됩니다.
  문제에서는 고려하지 않는 바깥쪽 면까지 포함한 값이죠.
• 오일러 지표 \( \chi \): 평면 그래프에서 이 값은 \( 2 \)입니다.

 

이제 식을 그대로 써보면 \( ((n+2)(m+2) + i) - ((n+1)(m+2) + (m+1)(n+2) + 2i) + (a+1) = 2 \)이고,

전개하고 정리하면 \( -nm - n - m - 1 - i + a = 0 \), 즉 \( a = (n+1)(m+1) + i \)가 됩니다.

 

3. 코드

vector<int> cs1, cs2;
inline int cvt(const vector<int>& v, int x){
    return lower_bound(all(v), x) - v.begin() + 1;
}
 
const int N = 131072;
int seg[262150];
void upd(int pos, int val){ pos += N-1;
    seg[pos] += val; pos >>= 1;
    while (pos){ seg[pos] = seg[pos<<1] + seg[pos<<1|1]; pos >>= 1; }
}
int qry(int st, int ed){ st += N-1; ed += N-1;
    int res = 0;
    while (st <= ed){
        if (st&1){ res += seg[st]; st += 1; }
        if (~ed&1){ res += seg[ed]; ed -= 1; }
        if (st > ed){ break; } st >>= 1; ed >>= 1;
    }
    return res;
}
 
pi2 arr[100020];
ll solve(int n){
    cs1.clear(); cs2.clear();
    for (int i = 1; i <= n; i++){
        cs1.push_back(arr[i].fr);
        cs2.push_back(arr[i].sc);
    }
    sort(all(cs1)); sort(all(cs2));
    sort(arr+1, arr+n+1);
    for (int i = 1; i < N+N; i++){ seg[i] = 0; }
    ll res = 0;
    for (int i = 1; i <= n; i++){
        int val = cvt(cs2, arr[i].sc);
        res += qry(val+1, N); upd(val, +1);
    }
    return res;
}
 
void Main(){
    int x, y, n, m; cin >> x >> y >> n >> m;
    ll ans = (n+1LL)*(m+1);
    for (int i = 1; i <= n; i++){ cin >> arr[i].fr >> arr[i].sc; }
    ans += solve(n);
    for (int i = 1; i <= m; i++){ cin >> arr[i].fr >> arr[i].sc; }
    ans += solve(m);
    cout << ans;
}