题解

几何化简

赛道是若干长方形横向首尾相接，且相邻矩形在竖直方向上有交集。最短路径一定由若干直线段拼接而成，并且只有在通过相邻两矩形共用的那条竖直边时才需要“拐弯”。因此我们只需要关心以下有限个候选点：起点 $S$、终点 $T$ 以及每一对相邻矩形重叠竖边上的上下两个端点。按照 $x$ 坐标排序后共有 $m \le 2n+2$ 个候选点。

任意合法路径都可以表示成在这些候选点之间顺次连线的折线。因为同一对矩形之间的重叠区间是一条竖线段，一旦选定在该竖边上的穿越点，高度更高或更低都会立即越界，所以从前一个候选点连到当前候选点的直线斜率必须处在“允许区间”里。

动态规划

设 dp[i] 表示从 $S$ 到第 $i$ 个候选点的最短距离。枚举前驱点 i，再尝试连接到每一个 j>i：

• 若 $x_i = x_j$，说明两点在同一竖直线，直接累加竖直距离即可；
• 否则，随着我们把候选点一个个加入，利用交叠区间的上下端点来不断收紧“可行斜率”区间 $[L,R]$。当遇到下端点时更新 $L$，遇到上端点时更新 $R$，只有 angle(Segment i→j) 落在区间内时线路才合法；
• 满足斜率约束后，用欧氏距离更新 dp[j]。

候选点个数与矩形个数同阶，因此该 DP 的状态数为 $O(n)$，转移一共枚举 $O(n^2)$ 对点即可完成。最后输出 dp[m-1] / v 即为最短时间。

复杂度

候选点数量不超过 $2n+2$，每个状态至多转移到其右侧的 $O(n)$ 个点，总时间复杂度 $O(n^2)$，空间复杂度 $O(n)$，可轻松通过 $n \le 2000` 的限制。

参考代码

#include <bits/allocator.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2")
#include <bits/stdc++.h>
using namespace std;
#define y1 _y1

const double eps = 1e-6;
const double inf = 1e9;

struct point {
	double Ox, Oy;
	point() {}
	point(double x, double y) : Ox(x), Oy(y) {}
	friend istream& operator >> (istream& in, point& o) {
		in >> o.Ox >> o.Oy;
		return in;
	}
	friend ostream& operator << (ostream& out, const point& o) {
		out << o.Ox << ' ' << o.Oy;
		return out;
	}
	friend point operator + (const point& A, const point& B) {return point(A.Ox + B.Ox, A.Oy + B.Oy);}
	friend point operator - (const point& A, const point& B) {return point(A.Ox - B.Ox, A.Oy - B.Oy);}
	friend point operator * (const point& A, const double& x) {return point(A.Ox * x, A.Oy * x);}
	friend point operator / (const point& A, const double& x) {return point(A.Ox / x, A.Oy / x);}
	double cross(const point& B) const {return Ox * B.Oy - Oy * B.Ox;}
	double cross(const point& B, const point& C) const {return (B - *this).cross(C - *this);}
	double dot(const point& B) {return Ox * B.Ox + Oy * B.Oy;}
	
	double angle() const {return atan2l(Oy, Ox);}
	point perp() const {return point(Oy, -Ox);} // rotate 90 ccw
	double length() const {return sqrtl(Ox * Ox + Oy * Oy);}
	double dist(const point& A) const {return (A - *this).length();}
	
	bool operator < (const point& O) const {
		if (abs(Ox - O.Ox) > eps) return Ox < O.Ox;
		return Oy < O.Oy;
	}
};

int x1[2008], y1[2008], x2[2008], y2[2008];
point A[4008];
double dp[4008];

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n; cin >> n;
	for (int i = 0; i < n; ++i) cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
	point S, E; cin >> S >> E;
	if (E < S) swap(S, E);
	int m = 1; A[0] = S;
	vector<int> Q;
	double l, r, cur; int yl, yr;
	for (int i = 0; i + 1 < n; ++i) if (S.Ox + eps < x2[i] && x2[i] < E.Ox + eps) {
		yl = max(y1[i], y1[i + 1]); yr = min(y2[i], y2[i + 1]);
		A[m] = point(x2[i], yl); ++m;
		A[m] = point(x2[i], yr); ++m;
	}
	A[m] = E; ++m;
	// for (int i = 0; i < m; ++i) {
		// cout << i << ' ' << A[i] << endl;
	// }
	double speed; cin >> speed;
	fill(dp, dp + m, inf); dp[0] = 0;
	for (int i = 0; i < m; ++i) {
		l = -4; r = 4; // radian
		for (int j = i + 1; j < m; ++j) {
			if (abs(A[i].Ox - A[j].Ox) < eps) {
				dp[j] = min(dp[j], dp[i] + A[i].dist(A[j]));
				continue;
			}
			if (j & 1) l = max(l, (A[j] - A[i]).angle());
			else r = min(r, (A[j] - A[i]).angle());
			cur = (A[j] - A[i]).angle();
			if (l - eps < cur && cur < r + eps) {
				dp[j] = min(dp[j], dp[i] + A[i].dist(A[j]));
				// cout << i << ' ' << j << ":\n";
				// cout << A[i] << ' ' << A[j] << endl;
				// cout << cur << ' ' << l << ' ' << r << endl;
			}
		}
	}
	cout << fixed << setprecision(9) << dp[m - 1] / speed << '\n';
}

`$nl