自动搬运

查看原文

来自洛谷，原作者为

	WhitD %$@oma

搬运于2025-08-24 22:50:15，当前版本为作者最后更新于2023-09-11 20:27:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

给定大小为 $m\times m$ 的二维平面，平面上有 $n$ 条线段，用端点坐标 $(x_1,y_1)$ 和 $(x_2,y_2)$ 表示。有一个点从 $(0,-\infty)$ 以 $v_y$ 的速度向 $y$ 轴正方向运动，终点为 $(0,\infty)$，对于一个 $v_x$ 值，点的水平速度可以在 $[-v_x,v_x]$ 内变化。你需要求出最小的 $v_x^*$，当点的水平速度 $v_x>v_x^*$ 时，点在运动过程中不会碰到任意一条线段。

思路

我们考虑点需要经过第 $i$ 条线段，此时最优路线一定会恰好经过 $i$ 的某个端点，并且点由一个端点到下一条需要经过的线段的某个端点的最优路线一定是直线，也就是总路线一定是一条经过若干条线段的端点的折线。

为什么嘞

根据速度公式，我们有 $v=\frac{\Delta x}{\Delta t}$，由于点的垂直速度 $v_y$ 是定值，因此 $\Delta t$ 也是一定的，此时 $v\propto\Delta x$，为了让所求的 $v_x^*$ 最小，$\left|\Delta x\right|$ 也必须最小，根据两点之间线段最短可知我们上述结论是成立的。

于是

我们可以先将所有线段按照他们端点的 $y$ 值升序排序，然后进行拓扑转移，设 $dp_i$ 表示到达第 $i$ 个端点所需要的最小水平速度 $v_x$ 的值，每次转移前需要判断这两个端点是否可以到达。

AC 代码

#include<bits/stdc++.h>
#define ls (i<<1)
#define rs (i<<1|1)
using namespace std;
struct node
{
    int x,y;
}nd[205];
struct line
{
    node f,l;
}ln[205];
int dis(node a,node b,node c){return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);}
int pos(int x){return (!x)?0:(x>0?1:-1);}
int is(line l1,line l2){return max(l2.f.y,l2.l.y)>min(l1.f.y,l1.l.y)&&max(l2.f.x,l2.l.x)>min(l1.f.x,l1.l.x)&&pos(dis(l2.f,l1.f,l2.l))*pos(dis(l2.f,l1.l,l2.l))<0&&max(l1.f.y,l1.l.y)>min(l2.f.y,l2.l.y)&&pos(dis(l1.f,l2.f,l1.l))*pos(dis(l1.f,l2.l,l1.l))<0&&max(l1.f.x,l1.l.x)>min(l2.f.x,l2.l.x); }
bool cmp(node a,node b){return a.y<b.y;}
int n,m,v;
double dp[205],ans=1e20;
int check(node a,node b)
{
	line x=line{a,b};
    for(int i=0;i<n;i++)
        if(is(x,ln[i])) 
			return 0;
    return 1;
}
int main()
{
	cin>>n>>m>>v;
	for(int i=0;i<2*n;i++)
		dp[i]=1e20;
    for(int i=0;i<n;i++)
        cin>>nd[ls].x>>nd[ls].y>>nd[rs].x>>nd[rs].y,ln[i]=line{nd[ls],nd[rs]};
    sort(nd,nd+2*n,cmp);
    for(int i=0;i<2*n;i++)
	{
        if(nd[i].x<=-m||nd[i].x>=m) 
			continue;
        if(check(node{nd[i].x,-10001},nd[i])) 
			dp[i]=0;
        for(int j=0;j<i;j++)
		{
            if(nd[j].y==nd[i].y) 
				break;
            if(check(nd[j],nd[i]))
                dp[i]=min(dp[i],max(dp[j],abs(1.0*(nd[i].x-nd[j].x)/(nd[i].y-nd[j].y))));
        }
        if(check(node{nd[i].x,10001},nd[i])) 
			ans=min(ans,dp[i]);
    }
    if(check(node{0,-10001},node{0,10001})) 
		ans=0;
    if(ans>1e10) 
		printf("-1");
    else 
    	printf("%.10lf",ans*v);
    return 0;
}