QOJ.ac

QOJ

時間限制: 1 s 記憶體限制: 256 MB 總分: 100

#6426. 对滑雪感兴趣

统计

Kotori 对滑雪很感兴趣。滑雪场是二维平面上沿 $y$ 轴延伸的无限长带状区域,其中所有点 $(x, y)$ 均满足 $-m \le x \le m$。滑雪时,Kotori 不能离开该区域,这意味着她的 $x$ 坐标绝对值始终不能超过 $m$。地面上还有 $n$ 条线段作为障碍物,Kotori 也不能穿过这些障碍物。

Kotori 将从 $(0, -10^{10^{10^{10^{10}}}})$(你可以将此 $y$ 坐标视为负无穷大)出发,向 $y$ 轴正方向移动。她的垂直速度(平行于 $y$ 轴)始终为 $v_y$,且不可改变;但她可以在区间 $[-v_x, v_x]$ 内控制她的水平速度(平行于 $x$ 轴)。Kotori 改变速度所需的时间可以忽略不计。

你的任务是帮助 Kotori 计算 $v_x^*$ 的最小值,使得当 $v_x > v_x^*$ 时,她能够安全地滑过滑雪场而不撞上任何障碍物。

输入格式

每个测试文件中仅包含一组测试数据。

第一行包含三个正整数 $n, m$ 和 $v_y$ ($1 \le n \le 100, 1 \le m \le 10^4, 1 \le v_y \le 10$),分别表示障碍物的数量、滑雪场的半宽以及垂直速度。

接下来的 $n$ 行中,第 $i$ 行包含四个整数 $x_1, y_1, x_2$ 和 $y_2$ ($-m \le x_1, x_2 \le m, -10^4 \le y_1, y_2 \le 10^4, x_1 = x_2$ 或 $y_1 = y_2$),表示第 $i$ 个障碍物是连接点 $(x_1, y_1)$ 和 $(x_2, y_2)$ 的线段,包含端点(即这两个点也是障碍物的一部分,不能触碰)。保证任意两个障碍物之间互不相交。

输出格式

输出一行,包含一个数字,表示 $v_x^*$ 的最小值。如果 Kotori 不可能滑过滑雪场,则输出 “-1”。

如果你的答案的绝对误差或相对误差不超过 $10^{-6}$,则视为正确。

样例

样例输入 1

3 2 1
-2 0 1 0
-1 4 2 4
0 1 0 3

样例输出 1

1.000000000000000

样例输入 2

2 1 2
-1 0 1 0
1 1 0 1

样例输出 2

-1

样例输入 3

2 3 7
-3 0 2 2
3 1 -2 17

样例输出 3

1.866666666666666

样例输入 4

1 100 1
-100 0 99 0

样例输出 4

0.000000000000000

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.