백준15305 경곽 침공

작성일 | In

문제 링크

  • http://icpc.me/15395

사용 알고리즘

  • DP

시간복잡도

  • $O(N^4)$

풀이

회전 각도에 제한이 있을 때 DP를 하는 것은 꽤 자주 보이는 유형입니다.

모노톤 체인 알고리즘과 비슷한 방식으로 볼록 껍질의 개수를 구할 것입니다. $D1(s, i, j)$를 $s$에서 시작해서 마지막에 $i\rightarrow j$ 변을 사용하는 위 껍질의 개수, $D2(s, i, j)$를 아래 껍질의 개수라고 정의합시다. 점들을 $(x, y)$ 오름차순으로 정렬하면 $O(N^4)$ 시간에 계산할 수 있습니다. 네제곱이지만 상수가 작아서 제한 시간 안에 계산할 수 있습니다.
실제 정답을 구하는 것은 시작점 $s$와 끝점 $j$를 고정한 다음, $\sum D1(s, i, j) \times \sum D2(s, i, j)$를 구하면 됩니다.

전체 코드

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
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
using ll = long long;
using Point = pair<ll, ll>;
constexpr unsigned MOD = 1e9+7;
inline void Add(uint32_t &a, const uint32_t b){ a += b; if(a >= MOD) a -= MOD; }
inline ll CCW(const Point &p1, const Point &p2, const Point &p3){
    return (p2.x-p1.x)*(p3.y-p2.y) - (p3.x-p2.x)*(p2.y-p1.y);
}

uint32_t N, D1[301][301][301], D2[301][301][301];
Point A[301];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N;
    for(int i=1; i<=N; i++) cin >> A[i].x >> A[i].y;
    sort(A+1, A+N+1);

    for(int s=1; s<N; s++){
        for(int i=s+1; i<=N; i++) D1[s][s][i] = 1;
        for(int i=s+1; i<=N; i++) for(int j=i+1; j<=N; j++) for(int k=s; k<i; k++) if(CCW(A[k], A[i], A[j]) < 0) Add(D1[s][i][j], D1[s][k][i]);
    }
    for(int s=1; s<N; s++){
        for(int i=s+1; i<=N; i++) D2[s][s][i] = 1;
        for(int i=s+1; i<=N; i++) for(int j=i+1; j<=N; j++) for(int k=s; k<i; k++) if(CCW(A[k], A[i], A[j]) > 0) Add(D2[s][i][j], D2[s][k][i]);
    }

    ll res = 0, up[301], lo[301];
    for(int s=1; s<N; s++){
        memset(up, 0, sizeof up);
        memset(lo, 0, sizeof lo);
        for(int i=s; i<=N; i++) for(int j=i+1; j<=N; j++) up[j] += D1[s][i][j], lo[j] += D2[s][i][j];
        for(int i=s; i<=N; i++) res = (res + up[i] * lo[i]) % MOD;
    }
    res -= 1LL * N * (N - 1) / 2;
    res %= MOD; if(res < 0) res += MOD;
    cout << res;
}