ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [Baekjoon - 16444] Contador de Pizza
    문제 풀이/Baekjoon Online Judge 2023. 3. 8. 09:24

    난이도: 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. 코드

    더보기
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    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;
    }
    cs
Designed by Tistory.