AOJ 2016 プールの監視員

• 問題概要

凸多角形の辺上を速度xで、内部を速度yで動ける点が辺上の点から内部の点に移動する時間の最小値を求めよ。(頂点数)<=10

• 解法

赤い辺が多角形の辺だとすると、真ん中の経路とるのであれば両端のどちらかの経路をとったほうがいいです(距離が適当な一次関数で表されるため)。

ということでプールの中を通るときはかならず片方の点はそれっぽい点(多角形の頂点か初期位置)です。もう片方の点の候補は(多角形は凸なのでプールから上がった点に飛び込むことは無意味なので)適当な三分探索で各辺あたり2つに絞られます。

ということで通りそうな点の個数はO(N^2)個くらいしかないのであとはワーシャルフロイドしてあげればO(N^6)で解けます。

テストケースが1000個くらいあるらしくTLEが厳しかった(dijkstraしろという話である)。あとepsを小さめにしないと誤差死するので注意。

実装がかるくていい感じ

以下コード(ライブラリは省略)

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<math.h>
#include<stdlib.h>
using namespace std;
double eps=1e-12;
double pi=3.1415926535897932384626433832;
double inf=1e+100;
double dist[300][300];
P optp(segm s,P p,double vg,double vw)
{
    P beg=s.first,end=s.second;
    for(int q=0;q<50;q++)
    {
        P m1=(beg+beg+end)/P(3,0),m2=(beg+end+end)/P(3,0);
        if(abs(m1-s.first)*vg+abs(m1-p)*vw>abs(m2-s.first)*vg+abs(m2-p)*vw)
        {
            beg=m1;
        }
        else
        {
            end=m2;
        }
    }
    return beg;
}
int main()
{
    for(;;)
    {
        int num;
        scanf("%d",&num);
        if(num==0)break;
        for(int i=0;i<300;i++)for(int j=0;j<300;j++)dist[i][j]=inf;
        poly vec;
        for(int i=0;i<num;i++)
        {
            double za,zb;
            scanf("%lf%lf",&za,&zb);
            vec.push_back(P(za,zb));
        }
        double vg,vw;
        scanf("%lf%lf",&vg,&vw);
        P st,go;
        double za,zb,zc,zd;
        scanf("%lf%lf%lf%lf",&za,&zb,&zc,&zd);
        st=P(za,zb);
        go=P(zc,zd);
        vector<P>dat;
        dat.push_back(st);
        dat.push_back(go);
        for(int i=0;i<num;i++)
        {
            for(int j=0;j<num;j++)
            {
                if(i==j)continue;
                dat.push_back(optp(make_pair(vec[i],vec[(i+1)%num]),vec[j],vg,vw));
                dat.push_back(optp(make_pair(vec[(i+1)%num],vec[i]),vec[j],vg,vw));
            }
        }
        for(int i=0;i<num;i++)
        {
            dat.push_back(optp(make_pair(vec[i],vec[(i+1)%num]),st,vg,vw));
            dat.push_back(optp(make_pair(vec[(i+1)%num],vec[i]),st,vg,vw));
            dat.push_back(optp(make_pair(vec[i],vec[(i+1)%num]),go,vg,vw));
            dat.push_back(optp(make_pair(vec[(i+1)%num],vec[i]),go,vg,vw));
        }
        for(int i=0;i<dat.size();i++)
        {
            for(int j=0;j<dat.size();j++)
            {
                dist[i][j]=dist[j][i]=vw*abs(dat[i]-dat[j]);
                for(int k=0;k<num;k++)
                {
                    if(ison(make_pair(vec[k],vec[(k+1)%num]),dat[i])&&ison(make_pair(vec[k],vec[(k+1)%num]),dat[j]))
                    {
                        dist[i][j]=dist[j][i]=min(dist[i][j],abs(dat[i]-dat[j])*vg);
                    }
                }
            }
        }
        for(int i=0;i<dat.size();i++)for(int j=0;j<dat.size();j++)for(int k=0;k<dat.size();k++)dist[j][k]=min(dist[j][k],dist[j][i]+dist[i][k]);
        printf("%.10lf\n",dist[0][1]);
    }
}