AOJ 1183 - Chain-Confined Path

計算ミスってた．

解法

幾何+DP．

2円の交点の求め方

円Aと円Bの交点を求める．

上図のように点をとる．AP，BP，ABの長さは既知であることに注意する．
このとき，AHとPHの長さが分かればいい．
三平方の定理より

ここで，より，連立方程式

が得られる．AHについて解くと，．
再び三平方の定理より．

コード

テンプレ部分は省略しています．

int N;
P ps[100], is[101][2];
double rs[100], dp[101][2];
 
double rec(int index, int which){
    if(index == N){return 0.0;}
    if(dp[index][which] > 0.0){return dp[index][which];}
     
    double res = 1e20;
    for(int i=index+1;i<=N;i++){
        for(int w=0;w<2;w++){
            int j;
            for(j=index+1;j<i;j++){
                if(!areIntersectedLines(is[index][which], is[i][w], is[j][0], is[j][1])){
                    break;
                }
            }
 
            if(j == i){res = std::min(res, rec(i, w) + dist(is[index][which] - is[i][w]));}
        }
    }
 
    return dp[index][which] = res;
}
 
int main(){
    while(scanf("%d", &N), N){
        for(int i=0;i<=N;i++){
            for(int j=0;j<2;j++){
                dp[i][j] = -1.0;
            }
        }
     
        for(int i=0;i<N;i++){
            double x, y;
            scanf("%lf %lf %lf", &x, &y, rs+i);
 
            ps[i].real(x);
            ps[i].imag(y);
        }
 
        is[0][0] = ps[0];
        is[N][0] = ps[N-1];
        is[N][1] = ps[N-1];
        for(int i=1;i<N;i++){
            P u = ps[i] - ps[i-1], v{-imag(u), real(u)};
            double d = dist(u);
            double x = 0.5 / d * (1.*d*d + rs[i-1]*rs[i-1] - rs[i]*rs[i]),
                y = std::sqrt(rs[i-1]*rs[i-1] - x*x);
         
            u = {real(u) / d * x, imag(u) / d * x};
            v = {real(v) / d * y, imag(v) / d * y};
         
            P w = u + v;
            is[i][0] = ps[i-1] + w;
 
            w = u - v;
            is[i][1] = ps[i-1] + w;
        }
 
        printf("%.6f\n", rec(0, 0));
    }
}