← 返回比赛

竞赛正在进行中 MMOI Round 3

← 上一题下一题 →

A7463 | $矿车交通$

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

> When I grew up and fell in love > I asked my sweetheart / What lies ahead > Will we have rainbows day after day > Here's what my sweetheart said: > Que sera, sera / Whatever will be, will be > The future's not ours to see > Que sera, sera / What will be, will be > > ——电影《擒凶记》插曲《Que Sera Sera》 > 未来，会是什么样的？ Alice 在服务器中建立起了一套完善的矿车交通体系。具体地，世界中有一条矿车轨道，从位置 $0$ 开始不断向右延伸。Steve 现在在位置 $x$，想要利用矿车到达位置 $y$，保证 $0\le x\le y$。 轨道上运行着 $n$ 辆矿车，其中的第 $i$ 辆拥有属性 $(t_i,v_i)$，表示这辆矿车会在第 $t_i$ 秒从位置 $0$ 出发，以 $v_i$ 米每秒的速度一直向右行驶。若某一个时刻 Steve 和矿车位置处于同一个位置，无论 Steve 是否已经坐在某辆矿车上，Steve 都可以瞬间转移到这辆矿车上。 特别地，Steve 也可以以不超过 $v_0$ 的速度朝任意方向行走。请你帮助 Steve 算出，最早在什么时候 Steve 能够到达位置 $y$？

输入格式

每个测试点包含多组测试数据 。输入的第一行包含两个正整数 $c,T$，分别表示测试点编号和测试数据的组数。对于每组测试数据： 第一行包含四个整数 $n,x,y,v_0$，分别表示矿车的数量、起点、终点的位置和 Steve 的行走速度。 接下来 $n$ 行，其中的第 $i$ 行包含两个整数 $t_i,v_i$，表示第 $i$ 辆矿车的属性。

输出格式

本题采用 Special Judge，只要你的答案和正确答案之间的相对误差或绝对误差不超过 $10^{-6}$，你的答案就会被认为是正确的。 对于每组测试数据，输出一行一个实数，表示 Steve 最早能在什么时候到达位置 $y$。

输入输出样例

输入 #1

输出 #1

7.333333333

【样例解释】 对于第一组测试数据，一种可能的方案为： * Steve 先一直向左走在 $\dfrac13$ 时刻于位置 $\dfrac23$ 与第 $1$ 辆矿车相遇并乘车； * Steve 乘第一辆矿车在 $6$ 时刻于位置 $12$ 与第 $2$ 辆矿车相遇并换乘； * Steve 乘第二辆矿车于 $\dfrac{22}{3}$ 时刻到达目标位置 $16$。 【数据范围】 测试点编号特殊性质$1-2$$n=1$$3-5$$T\le10,n\le100$$6-7$$v_0=0$$8-10$无 对于 $100\%$ 的测试点，保证：$1\le T\le 10^4$，$1\le n\le 2\times 10^5$，$0\le x,y,v_0,t_i\le 10^9$，$1\le v_i\le 10^9$，单个测试点中所有测试数据的 $n$ 之和不超过 $2\times 10^5$。

C++ 编辑器

输入

输出