QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 256 MB Total points: 100

#578. 灯

Statistics

深夜,Bitratio 打开了 Byteasar 所住大楼入口处的灯。现在,强光让 Byteasar 无法入睡。虽然灯光没有直接照在 Byteasar 的窗户上,但它通过其他窗户的反射照了进来。由于无法入睡,Byteasar 变得非常烦躁。为了缓解这种情况,他试图转移注意力,但他满脑子想的都是那道光。于是,Byteasar 望向窗外,想知道他的邻居们是否也遭受着同样的折磨,即光线是否也照在了他们的窗户上。在他看来,这是一个有趣的问题。你比预想中更早地接触到了这个难题:由于无法独自解决这个问题,且现在根本无心睡眠(无论是他的还是你的),Byteasar 打电话向你求助。你很了解他,明白如果不写出一个程序来解决他的问题,你自己也别想睡觉了。

Byteasar 住在 $B$ 大楼,楼里有 $n$ 扇窗户。灯位于该大楼底部的一面墙上。在 $B$ 大楼对面,距离正好 10 米处,有另一栋大楼 $C$。这栋有 $m$ 扇窗户的大楼的墙面与 Byteasar 所住的 $B$ 大楼的墙面平行。

灯光的行为符合预期,即遵循几何光学(或射线光学)的规律。具体来说,光线沿射线传播,如果光线射中窗户,它就会发生反射。根据反射定律,反射角等于入射角。

我们在两栋大楼的墙面上引入坐标系,方式如下:两个 $X$ 轴均为水平方向,两个 $Y$ 轴均为垂直方向;两面墙上的坐标轴方向一致,且两面墙上的 $(0,0)$ 点互相对齐。窗户(在任何一栋楼上)都是边平行于坐标轴的矩形。光线仅在窗户的内部发生反射;在窗户边界上会被吸收。在每一栋楼中,任意两扇窗户的内部互不重叠。灯位于 $B$ 大楼墙上的 $(0,0)$ 点,该点既不在任何窗户的内部,也不在任何窗户的边界上。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 600$),用空格分隔,分别表示第一栋楼和第二栋楼的窗户数量。接下来的 $n$ 行描述 Byteasar 所住大楼($B$ 大楼)的窗户,每行描述一扇窗户。

第 $(i+1)$ 行($1 \le i \le n$)包含四个整数 $x_{1,i}, y_{1,i}, x_{2,i}, y_{2,i}$ ($-1,000 \le x_{1,i} < x_{2,i} \le 1,000$, $0 \le y_{1,i} < y_{2,i} \le 1,000$),用空格分隔。这四个数表示 $B$ 大楼的第 $i$ 扇窗户是一个矩形,其左下角和右上角的坐标(单位为米)分别为 $(x_{1,i}, y_{1,i})$ 和 $(x_{2,i}, y_{2,i})$。

接下来的 $m$ 行以类似的方式描述 $C$ 大楼的窗户。

输出格式

第一行输出被光线射中内部的 $B$ 大楼窗户的数量。你可以假设在每个测试用例中,至少会有一扇这样的窗户(即 Byteasar 的窗户)。

第二行按升序输出这些窗户的编号(窗户编号从 $1$ 开始),用空格分隔。

样例

输入 1

3 3
-1 2 1 4
-1 5 1 7
-3 8 -2 20
-1 1 1 2
-1 4 1 5
-1 7 1 10

输出 1

2
1 2

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.