ACM-ICPC 2012 国内予選 Problem E 鎖中経路

鎖中経路

※コンテスト本番の入力が通るかどうかは未確認

サンプルの図を見ると、最短経路は、両端の円の中心といくつかの円の交点を直線で結べば得られることがわかる。一方の円の中心からそれぞれの交点に到達するまでの最短経路を覚えておき、動的計画法。交点Aから交点Bまで直線で行けるのは、その直線が、途中全ての交点を結んだ線分と交差する場合。

#include <iostream>
#include <vector>
#include <complex>
using namespace std;

typedef complex<double> comp;

//  外積
double cross( comp a, comp b ) { return a.real()*b.imag()-a.imag()*b.real(); }

//  a1とa2を結ぶ線分と、b1とb2を結ぶ線分が交差しているか
bool inter( comp a1, comp a2, comp b1, comp b2 )
{
    return cross(a2-a1,b1-a1) * cross(a2-a1,b2-a1) <= 0 &&
           cross(b2-b1,a1-b1) * cross(b2-b1,a2-b1) <= 0;
}

int main()
{
    while ( true )
    {
        int n;  cin>>n;
        if ( n==0 )
            break;
        vector<comp> p(n);
        vector<double> r(n);
        for ( int i=0; i<n; i++ )
        {
            int x, y;  cin>>x>>y>>r[i];
            p[i] = comp(x,y);
        }

        //  両端の円の中心と交点
        vector<vector<comp> > C(n+1,vector<comp>(2));
        C[0][0] = C[0][1] = p[0];
        for ( int i=1; i<n; i++ )
        {
            comp p1 = p[i-1];
            comp p2 = p[i];
            double r1 = r[i-1];
            double r2 = r[i];
            double d = abs(p2-p1);
            double th = acos((d*d+r1*r1-r2*r2)/(2*d*r1));
            C[i][0] = p1 + polar( r1, arg(p2-p1)+th );
            C[i][1] = p1 + polar( r1, arg(p2-p1)-th );
        }
        C[n][0] = C[n][1] = p[n-1];

        //  交点C[i][j]までの最短経路
        vector<vector<double> > D(n+1,vector<double>(2,1e10));
        D[0][0] = D[0][1] = 0;

        for ( int ti=1; ti<n+1; ti++ )
        for ( int tj=0; tj<2; tj++ )
        {
            for ( int fi=0; fi<ti; fi++ )
            for ( int fj=0; fj<2; fj++ )
            {
                bool f = true;
                for ( int i=fi+1; i<ti && f; i++ )
                    if ( !inter(C[fi][fj],C[ti][tj],C[i][0],C[i][1]) )
                        f = false;
                if ( f )
                    D[ti][tj] = min( D[ti][tj], D[fi][fj]+abs(C[ti][tj]-C[fi][fj]) );
            }
        }

        printf( "%.10f\n", D[n][0] );
    }

    return 0;
}