勾肥大战

时间限制: 1000 ms 内存限制: 131072 kb
总通过人数: 0 总提交人数: 0

题目描述

一天晚上, Cabinfever 熟练地打开了 steam ,又打开了 dota2 ,但他今天不是很想玩单人排位赛,所以开始找有趣的 RPG 地图玩。 Cabinfever发现了一张叫勾肥大战的地图, Cabinfever 平时就很喜欢玩屠夫,所以就玩了起来。

勾肥大战是这样一个地图模式:玩家分为两个阵营,地图上有一个峡谷将他们分开。每个玩家都控制一个屠夫,屠夫可以发射肉钩,发射后肉钩的起点不会因为屠夫的移动而改变,因此钩子的轨迹为射线。除了不能越过峡谷外,屠夫可以自由移动,但被对方阵营的钩子勾到就会受到伤害并且被勾走,勾到的定义是存在某一时刻屠夫与钩子在同一点。此外,由于装备的存在,每位玩家的肉钩速度与移动速度都可能不同。

但是 Cabinfever 太菜了,被虐的很惨,这让 Cabinfever 晚上做梦也梦到了在玩勾肥大战。在梦里,己方阵营有 $n$ 位玩家,敌方阵营有 $m$ 位玩家。不妨将地图视为无穷大的二维平面坐标系,并且峡谷与 Y 轴重合,这意味着两个阵营的屠夫被 Y 轴分开,不可逾越。已知所有玩家的位置和己方玩家的肉钩速度,以及敌方玩家的移动速度。

定义出钩角度出钩方向与 Y 轴正向的夹角,而且 Cabinfever 认为只要有可能勾到对方屠夫的出钩角度,都可以称为一个好的出钩角度。现在,假定每个屠夫都不会影响同一阵营的屠夫的肉钩在出钩方向的位移, Cabinfever 想知道每个己方玩家在当前位置所具有的好的出钩角度的范围(详细的说明参见输出格式)。

solution1

输入

第一行包含一个正整数 $T$ ,表示有 $T$ 组测试数据。

接下来依次给出每组测试数据。对于每组测试数据:

第一行有两个正整数 $n$ 和 $m$ 。

接下来 $n$ 行,第 $i$ 行有两个整数 ${ax}_i$ 和 ${ay}_i$ ,表示第 $i$ 位己方玩家的屠夫位置。

接下来 $m$ 行,第 $i$ 行有两个整数 ${bx}_i$ 和 ${by}_i$ ,表示第 $i$ 位敌方玩家的屠夫位置。

接下来一行 $n$ 个数,第 $i$ 个正整数 $a_i$ 表示第 $i$ 位己方玩家的屠夫的肉钩速度。

接下来一行 $m$ 个数,第 $i$ 个正整数 $b_i$ 表示第 $i$ 位敌方玩家的屠夫的移动速度。

保证在一行中的每个整数之间有恰好一个空格,没有其他额外的空格。

$1 \leq T \leq 10, 1 \leq n,m \leq 1000, 0 < a_i, b_i < 100, \min(a_i) > \max(b_j)$

$-1000 < {ax}_i < 0 < {bx}_i < 1000,-1000 < {ay}_i, {by}_i < 1000$

输出

对于每组数据输出 $n$ 行,第 $i$ 行包含两个实数 $\theta_1, \theta_2$ ,表示第 $i$ 位己方玩家的屠夫的好的出钩角度最小值是 $\theta_1$ ,而最大值是 $\theta_2 (0 < \theta_1 < \theta_2 < \pi)$。

对于本题,输出的实数需要精确到小数点后恰好两位,输出中在一行的每个实数之间用恰好一个空格隔开,不能有其他额外空格。

输入样例

2
1 1
-1 0
1 0
3
1
2 2
-2 0
-1 0
1 1
1 -1
10 10
1 1

输出样例

1.23 1.91
1.15 1.99
1.01 2.13

Author: Cabinfever

相关推荐