QOJ.ac

QOJ

حد الوقت: 3 s حد الذاكرة: 64 MB مجموع النقاط: 100

#16019. 云

الإحصائيات

天空中有 $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

该图显示了从上方看到的云。虚线标记了将穿过激光束的点。

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.