← 返回题目列表

Codeforces · 28/E

E. DravDe 拯救世界

中文机器翻译题面 查看原题

太可怕了!银河鸡帝国试图征服一座美丽的城市“Z”,他们建造了一个巨大的孵化器,每天可以生产数百万只鸡兵,并用栅栏围起来。巨大的培养箱看起来就像是 Oxy 平面上的一个有 n 个顶点的多边形。德拉夫德自然不能坐以待毙,他要毁灭吃鸡帝国。当然,他将从孵化器开始。

DravDe 完全位于 A(xa, ya) 点孵化器的领土之外,并且想要进入并杀死在那里工作的所有鸡。但这需要做很多事情!问题是,DravDe 最近去滑旱冰,双腿骨折了。他将乘坐他的喷气式飞机 LEVAP-41 到达孵化器的领地。

LEVAP-41 以速度 V(xv, yv, zv) 飞行。 DravDe可以在A点上飞机,飞行一段时间,然后自己空投。 DravDe 非常重,这就是为什么他以速度 Fdown 垂直下落,但在自由落体的每个点上,DravDe 都可以打开降落伞,从那一刻起他开始以风速 U(xu, yu, zu) 下落,直到落地。不幸的是,DravDe 不擅长数学。你会帮助可怜的世界救世主找到这样一个空投计划,让他降落在孵化器的领土上吗?如果答案不唯一,DravDe 希望找到他在飞机上飞行时间最短的计划。如果答案仍然有多个,他想找到在打开降落伞之前自由落体时间最短的一个

输入

第一行包含数字 n (3 ≤ n ≤ 104) — 栅栏的顶点数量。接下来的 n 行包含这些顶点的坐标(两个整数 xi,yi),按顺时针或逆时针顺序排列。可以保证栅栏不包含自相交。

下面四行包含点A的坐标(xa,ya),速度V(xv,yv,zv),Fdown和速度U(xu,yu,zu)。所有输入的数字都是整数。所有坐标的绝对值不超过104。可以保证 zv > 0 且 Fdown、zu < 0,并且 A 点严格位于孵化器的区域之外。

输出

第一行输出两个数字t1、t2,如果DravDe在时间t1(从飞行开始算起)降落,他就降落在孵化器的领土上(降落在边界上被视为降落在领土上)。如果DravDe没有打开降落伞,第二个数字应该等于DravDe下落的持续时间。如果DravDe无法到达孵化器的领地,则输出-1 -1。如果答案不唯一,则输出t1最小的答案。如果答案仍然有多个,则输出t2最小的答案。您的答案的绝对或相对误差必须小于 10 - 6。

示例

输入 #1

4
0 0
1 0
1 1
0 1
0 -1
1 0 1
-1
0 1 -1

输出 #1

1.00000000 0.00000000

输入 #2

4
0 0
0 1
1 1
1 0
0 -1
-1 -1 1
-1
0 1 -1

输出 #2

-1.00000000 -1.00000000

输入 #3

4
0 0
1 0
1 1
0 1
0 -1
1 1 1
-1
1 1 -1

输出 #3

0.50000000 0.00000000