← 返回题目列表

Codeforces · 47/E

E. 大炮

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

伯敦被围攻!袭击者封锁了所有的出路,他们的大炮正在轰炸这座城市。幸运的是,贝尔兰德情报部门成功拦截了敌人的射击计划。我们先介绍一下笛卡尔坐标系,其原点与大炮的位置重合,Ox轴指向城市方向向右,Oy轴指向上方(指向天空)。大炮还会发射 n 次。所有射击中炮弹的初始速度都是相同的,并且等于 V,因此每次射击都只有一个数字 alphai 来表征,该数字代表大炮开火的角度。由于大炮的技术特点,该角度不超过 45 个角度 (π / 4)。我们忽略大炮的尺寸并考虑从 (0, 0) 点发射。

球根据以一定角度抛向地平线的已知物理定律飞行:

vx(t) = V·cos(alpha)

vy(t) = V·sin(alpha) – g·t

x(t) = V·cos(alpha)·t

y(t) = V·sin(alpha)·t – g·t2 / 2

认为重力加速度 g 等于 9.8。

Bertown 保卫着 m 堵墙。第 i 面墙表示为垂直线段 (xi, 0) - (xi, yi)。当球撞到墙上时,它会卡在墙上而不会继续飞行。如果球没有撞到任何墙壁,它就会落在地面上 (y = 0) 并停止。如果球正好击中点 (xi,yi),则视为卡住。

你的任务是找到每个球最终所在点的坐标。

输入

第一行包含整数 n 和 V (1 ≤ n ≤ 104, 1 ≤ V ≤ 1000),分别代表击球次数和每个球的初始速度。第二行包含 n 个空格分隔的实数 alphai (0 < alphai < π / 4),它们代表大炮发射的角度(以弧度为单位)。第三行包含整数 m (1 ≤ m ≤ 105),表示墙的数量。然后是 m 行,每行包含两个实数 xi 和 yi (1 ≤ xi ≤ 1000, 0 ≤ yi ≤ 1000),代表墙的坐标。所有实数的小数位数不超过 4 位。壁可以部分重叠或者甚至重合。

输出

打印 n 行,每行包含两个实数 — 计算每个球的着陆点坐标。您的答案的相对或绝对误差应小于 10 - 4。

示例

输入 #1

2 10
0.7853
0.3
3
5.0 5.0
4.0 2.4
6.0 1.9

输出 #1

5.000000000 2.549499369
4.000000000 0.378324889

输入 #2

2 10
0.7853
0.3
2
4.0 2.4
6.0 1.9

输出 #2

10.204081436 0.000000000
4.000000000 0.378324889