[Baekjoon - 2144] 울타리 넘기

난이도: Gold I

 

태그

• Dynamic Programming
• Line Intersection

 

풀이

0. 풀이를 읽기 전: 정의

• \( P_{i} \)는 \( i \)번째 점의 위치를 의미합니다.
  • 시작점은 \( P_{0} \), 즉 \( 0 \)번째 점으로 표현합니다.
• \( L_{i} \)는 \( i \)번째 울타리의 위치 (선분)을 나타냅니다.
• \( H_{i} \)는 \( i \)번째 울타리의 높이를 나타냅니다.

 

1. \( P_{i} \)에서 \( P_{j} \)로 성공적으로 이동할 수 있는 확률은?

어떤 울타리 \( L_{k} \)와 \( \overline{P_{i} P_{j}} \)가 교차한다면, 이 울타리를 뛰어넘을 확률은 \( \frac{1}{H_{k}} \)가 됩니다.

그러므로, 모든 울타리를 보면서 \( L_{k} \)와 \( \overline{P_{i} P_{j}} \)가 교차한다면, 확률에 \( \frac{1}{H_{k}} \)를 곱해주면 됩니다.

 

이 문제에서는 세 점이 한 직선 위에 놓이는 경우는 교차하지 않음으로 판정하면 \( 1 \)의 확률로 뛰어넘는다 를 잘 처리할 수 있습니다.

 

이러한 확률을 \( O(N^2F) \) 시간에 계산해둔 뒤, \( A_{i, j} \)라고 부릅시다.

단, 계산의 편의를 위해 \( A_{i, i} = 0 \)으로 두는 것을 추천합니다.

 

2. 그렇다면, \( k \)번 이동해서 \( P_{i} \)로 이동할 수 있는 확률은?

\( dp_{k, i} \) = \( k \)번 이동해서 \( P_{i} \)로 이동할 수 있는 확률 을 정의해봅시다.

 

초항은, \( 0 \)번 이동했을 때 \( dp_{0, 0} = 1 \), \( dp_{0, i} = 0 \)입니다.

점화식은, \( k-1 \)번 이동해서 \( P_{j} \)로 온 뒤, \( P_{j} \rightarrow P_{i} \)의 이동을 하는 것을 생각해보면

\( dp_{k, i} = \max dp_{k-1, j} \cdot A_{j, i} \)가 됩니다.

 

주의할 점은, 점화식 계산 중에는 \( 0 \)번 점으로 돌아가면 안 됩니다!

 

3. 문제의 답은?

\( K \)번의 이동을 한 뒤, 다시 시작점으로 돌아와야 계산이 끝나겠죠.

이는, \( dp_{K, *} \)까지 계산을 끝낸 뒤에, \( P_{i} \rightarrow P_{0} \)의 이동까지 처리한 값인

\( \max dp_{K, i} \cdot A_{i, 0} \)을 출력해주면 됩니다.

 

4. 코드

int ccw(pl2 p1, pl2 p2, pl2 p3){
    ll a = p1.sc*p2.fr + p2.sc*p3.fr + p3.sc*p1.fr;
    ll b = p1.sc*p3.fr + p3.sc*p2.fr + p2.sc*p1.fr;
    return sgn(a-b);
}
 
bool crs(pl4 l1, pl4 l2){
    pl2 p1 = l1.fr, p2 = l1.sc;
    pl2 p3 = l2.fr, p4 = l2.sc;
    int r123 = ccw(p1, p2, p3), r124 = ccw(p1, p2, p4);
    int r341 = ccw(p3, p4, p1), r342 = ccw(p3, p4, p2);
    if (r123 == 0 || r124 == 0 || r341 == 0 || r342 == 0){ return 0; }
    if (r123 != r124 && r341 != r342){ return 1; }
    return 0;
}
 
pl2 arr[120]; pl5 brr[220];
 
ld adj[120][120];
ld dp[520][120];
 
void Main(){
    int n, m, k; pl2 p; cin >> n >> k >> m >> arr[0].fr >> arr[0].sc;
    for (int i = 1; i <= n; i++){ cin >> arr[i].fr >> arr[i].sc; }
    for (int i = 1; i <= m; i++){
        cin >> brr[i].fr.fr.fr >> brr[i].fr.fr.sc
            >> brr[i].fr.sc.fr >> brr[i].fr.sc.sc >> brr[i].sc;
    }
    for (int i1 = 0; i1 <= n; i1++){
        for (int i2 = 0; i2 <= n; i2++){
            adj[i1][i2] = 1;
            if (i1 == i2){ adj[i1][i2] = 0; continue; }
            if (i1 > i2){ adj[i1][i2] = adj[i2][i1]; continue; }
            for (int j = 1; j <= m; j++){
                if (crs({arr[i1], arr[i2]}, brr[j].fr)){ adj[i1][i2] *= (ld)1/brr[j].sc; }
            }
        }
    }
    /*for (int i1 = 0; i1 <= n; i1++){
        for (int i2 = 0; i2 <= n; i2++){
            cout << "ADJ " << i1 << ' ' << i2 << " = " << adj[i1][i2] << endl;
        }
    }*/
    dp[0][0] = 1;
    for (int i = 1; i <= k; i++){
        for (int p1 = 0; p1 <= n; p1++){
            for (int p2 = 1; p2 <= n; p2++){
                dp[i][p2] = max(dp[i-1][p1]*adj[p1][p2], dp[i][p2]);
            }
        }
        //for (int p = 1; p <= n; p++){ cout << "DP " << i << ' ' << p << " = " << dp[i][p] << endl; }
    }
    ld ans = 0;
    for (int p = 1; p <= n; p++){ ans = max(ans, dp[k][p]*adj[p][0]); }
    //for (int p = 1; p <= n; p++){ cout << "RES " << p << " = " << dp[k][p]*adj[p][0] << endl; }
    printf("%.4Le", ans);
}