天空中有 $n$ 朵云,它们都在风的作用下以相同的恒定速度 $v = (v_x, v_y)$ 连续运动。也就是说,对于任何实数 $t \ge 0$,初始坐标为 $(x, y)$ 的云上某点在时刻 $t$ 的位置为 $(x + t \cdot v_x, y + t \cdot v_y)$。
为简单起见,我们假设每朵云都是一个多边形(包含其边界),其顶点的初始坐标为整数。该多边形不一定是凸多边形,但其任意两条边不能自交(相邻边的公共端点除外)。云之间可能会发生重叠。
地面上有一个卫星控制中心,坐标为 $(0, 0)$,在控制中心正上方、云层上方有一颗卫星。从控制中心向卫星垂直向上发射一束激光。激光用于与卫星进行通信。然而,当激光束穿过云层时,通信将无法进行。最初,激光束不穿过任何云。在观测期间,可能会有若干个时刻,激光束穿过一朵(或多朵)云,从而中断通信。即使激光束仅穿过云的一个顶点,通信也会瞬间中断。你需要编写一个程序,计算在所有云都飘走之前,通信被中断了多少次。
任务
编写一个程序,满足以下要求:
- 从标准输入读取云的位置、形状和速度,
- 确定通信被中断的次数,
- 将结果写入标准输出。
输入格式
输入的第一行包含三个整数 $n, v_x$ 和 $v_y$,由单个空格分隔,$1 \le n \le 1000$,$-1\,000\,000\,000 \le v_x, v_y \le 1\,000\,000\,000$;$n$ 是云的数量,$v = (v_x, v_y)$ 是云的速度向量($v \neq (0,0)$)。$x$ 坐标对应东西方向,$y$ 坐标对应南北方向。
接下来的 $n$ 行描述了这些云,每行一朵云。这些行中的每一行都由一个整数序列组成,由单个空格分隔。第一个整数是该云的顶点数 $k$,$3 \le k \le 1000$。紧接着是 $2k$ 个整数:$x_1, y_1, x_2, y_2, \dots, x_k, y_k$,$-1\,000\,000\,000 \le x_i, y_i \le 1\,000\,000\,000$;$(x_1, y_1), (x_2, y_2), \dots, (x_k, y_k)$ 是顺时针方向上连续顶点的坐标。
激光束穿过云边界的次数最多为 $100\,000$ 次。
输出格式
输出的第一行且仅有一行应包含恰好一个整数:通信被中断的次数。
样例
输入样例 1
4 -2 -1 4 6 2 6 4 8 4 8 2 4 2 3 1 -1 2 5 4 2 3 -3 1 -1 2 -1 -1 5 5 3 3 3 5 6 5 6 -1
输出样例 1
3
说明 1
该图显示了从上方看到的云。虚线标记了将穿过激光束的点。