算法1

(计算几何)

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;

int n,w,v,u;//多边形点数，路线长度，车速，人的最大速度
double ans;
double eps=1e-8;
struct Line
{
    int x,y;
}a[10010];

int main()
{
    cin>>n>>w>>v>>u;
    double k0=1.00000000*u/v;
    int above=0,below=0;//分别表示直线y=(u/v)x上方，下方的多边形顶点数量
    for(int i=1;i<=n;i++)
    {
        int x,y;
        cin>>x>>y;
        a[i].x=x;  a[i].y=y;
        double k=1.00000000*y/x;
        if(x*k0<y) above++;
        else if(x*k0>y) below++;
        else above++,below++;
    }
    if(below==n||above==n)//整个多边形在直线的上方或下方，可以全速冲刺（因为这样代表着多边形内的任何一个点都会比奶牛晚到或早到，进而代表不会被撞到）
    {
        ans=1.00000000*w/u;
    }
    else//直线穿过了该多边形，需要将直线向下平移
    {
        double b=1e9;//直线斜率确定，找截距b的最大值(b<=0)
        //截距b的最大值是经过多边形上某一点，且斜率为u/v的某一直线，这些直线中b的最小值
        for(int i=1;i<=n;i++)
        {
            int x=a[i].x,y=a[i].y;
            b=min(b,y-k0*x);
        }
        b=min((double)0,b);
        ans=1.00000000*(w-b)/u;
    }
    printf("%.10lf",ans);
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla