QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 1024 MB Total points: 100

#3620. 学者的草坪

Statistics

剑桥大学有一个著名的传统,且常被其他学校效仿,即“学者草坪”(Scholar’s Lawn)——这是一片草地,学校的院士(Fellow)或其他尊贵人士可以在上面行走,但普通学生不行。

因此,如果一名学生发现一位院士正穿过校园,并希望“伏击”……呃,是与他们偶遇,那么该学生只能沿着草地中铺设的一系列狭窄的人行道行走,希望能赶在院士到达之前或同时到达院士的路径上。院士路径的终点是学术圣林(Sacred Grove of Academe),学生禁止进入该区域,因此如果院士在学生到达之前就进入了圣林,学生就没机会了。

例如,图 1 展示了一片草坪,其中包含固定的铺设人行道(实线)和院士所走的路径(虚线);$F$ 和 $S$ 分别表示院士和学生的初始位置。如果两人以相同的速度(例如每秒一米)行进,那么在 17.67767 秒后,院士会发现学生正在位置 $(22.5, 12.5)$(由小空心圆“◦”标记)处等待交谈。

图 1:样例输入 1

输入格式

输入首先包含一个整数 $n$,$1 \le n \le 500$,表示直线人行道的数量。接下来有 $n$ 行,每行包含 4 个整数,表示每条人行道的端点 $(x, y)$ 坐标。之后是一行,包含三个实数 $x_s, y_s, v_s$,其中 $(x_s, y_s)$ 是学生的位置,$v_s$($0 < v_s \le 1\,000$)是学生的行走速度。保证点 $(x_s, y_s)$ 位于 $n$ 条铺设人行道中的某一条上。最后一行包含 5 个数字。前 4 个数字是实数 $x_{1f}, y_{1f}, x_{2f}, y_{2f}$,$-10\,000 \le x_{1f}, y_{1f}, x_{2f}, y_{2f} \le 10\,000$,给出了院士的起始位置 $(x_{1f}, y_{1f})$ 和结束位置 $(x_{2f}, y_{2f})$(学生能接触到院士的最后一点)。最后一个数字是实数 $v_f$($0 < v_f \le 1\,000$),给出了院士的行走速度。所有实数输入最多有四位小数。

院士总是沿直线行走。学生只能沿着人行道行走,人行道被视为宽度为零。如果一条人行道与另一条人行道或院士的路径相交,它们将交于一点。共线的人行道互不相交;同样,如果院士的路径与某条人行道共线,它们也不会相交。

输出格式

输出学生与院士在人行道与院士路径的交点处能够相遇的最早时间 $t$。如果不可能相遇,输出单词“Impossible”。数值答案应精确到 $10^{-6}$ 的绝对或相对误差范围内。

样例

输入 1

7
5 5 35 5
35 0 15 20
30 0 30 10
30 10 35 10
35 10 35 15
35 15 30 15
30 15 30 30
30.0 0.0 1.0
10 0 40 30 1.0

输出 1

17.67766953

输入 2

7
5 5 35 5
35 0 15 20
30 0 30 10
30 10 35 10
35 10 35 15
35 15 30 15
30 15 30 30
30.0 0.0 1.0
10 0 40 30 1.2

输出 2

Impossible

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.