[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^{2}F)$ 시간에 계산해둔 뒤, $A_{i,j}$라고 부릅시다.

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

 

2. 그렇다면, $k$번 이동해서 $P_i$로 이동할 수 있는 확률은?

$d{p}_{k,i}$ = $k$번 이동해서 $P_i$로 이동할 수 있는 확률 을 정의해봅시다.

 

초항은, $0$번 이동했을 때 $d{p}_{0,0}=1$, $d{p}_{0,i}=0$입니다.

점화식은, $k-1$번 이동해서 $P_j$로 온 뒤, $P_j\to P_i$의 이동을 하는 것을 생각해보면

$d{p}_{k,i}=maxd{p}_{k-1,j}\cdot A_{j,i}$가 됩니다.

 

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

 

3. 문제의 답은?

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

이는, $d{p}_{K,\ast }$까지 계산을 끝낸 뒤에, $P_i\to P_0$의 이동까지 처리한 값인

$maxd{p}_{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);
}