2456 「POI2010」灯 Lamp

译自 POI 2010 Stage 3. Day 1「Lamp」

在夜深人静的夜晚里，Bitratio 打开了 Byteasar 所在建筑物门口的灯。灯发出的强光导致 Byteasar 无法睡觉。尽管灯没有直接照在 Byteasar 的窗户上，却通过其他的窗户反射进入了 Byteasar 的卧室。Byteasar 由于无法睡觉而感到烦躁。他很好奇他的邻居是否也受到了同样的干扰，于是他来向你求助。你很了解他，因此你清楚地明白，在写出程序并解出这个问题之前你也无法入眠。

Byteasar 住在建筑物 B 里，有 $n$ 个窗户。灯在这个建筑物最下方的一个墙上。在建筑物 $B$ 的对面恰好 $10$ 米有另一个建筑物 C，且这个建筑物的墙与 B 建筑物的墙平行。

灯光的传播方式与物理学定律一样，遇到窗户时会发生反射。灯光的反射满足反射定律，即入射角等于出射角。

我们以如下方式定义两个建筑物的墙的坐标系统。两个建筑物的 X 轴都是水平的，而 Y 轴都是竖直的。两堵墙的坐标轴方向是相同的，且两堵墙上的 $(0,0)$ 坐标恰好面对面。每一个窗户用坐标系中一个四条边与坐标轴平行的矩形表示。一条光线只在窗户的内部被反射，在窗户的边界上会被吸收。光源在 B 建筑物的原点上，保证该点不在任何一个窗户的边界或内部。

第一行有两个整数 $n,m$ ，分别表示第一个建筑物和第二个建筑物的窗口个数。

接下来 $n$ 行表示 B 建筑的窗户。第 $(i+1) (1 \le i \le n)$ 行含有四个整数 $x_{1,i}, y_{1,i}, x_{2,i}, y_{2,i} $ ，用空格分隔，表示 B 建筑的第 $i$ 个窗口是一个矩形，且其左下角坐标为 $x_{1,i}, y_{1,i}$ ，右上角坐标为 $x_{2,i}, y_{2,i}$ 。

接下来 $m$ 行以相同格式表示 C 建筑的窗户。

第一行输出 B 建筑中受到光线照射的窗口数量。因为 Byteasar 正在受到强光照射，你可以认为至少有一个这样的窗口。

第二行按从小到大的顺序输出 B 建筑受到光线照射的窗口编号，用空格分隔。

一条光线经过 C 建筑的第一个窗口反射后会照射到 B 建筑的第一个窗口（例如光线可能在 $(0, 1.5)$ 位置照射 C 建筑后被反射到 B 建筑的 $(0, 3)$ 位置）。要照射到 B 建筑的第二个窗口，这条光线至少要被反射三次。例如，该光线会从 B 建筑反射到 C 建筑的 $(0, 4.5)$ 位置处（在 C 建筑的第二个窗口内），并照射在 B 建筑的 $(0, 6)$ 位置处。没有光线会照到 B 建筑的第三个窗口。事实上，C 建筑的每个窗口都被光线照射过，但上图只画出了照射过某个 B 建筑窗口的光线。

对于 $100\%$ 的数据， $1\le n,m\le 600,-1000 \le x_{1,i} \lt x_{2,i} \le 1000,0 \le y_{1,i} < y_{2,i} \le 1000$ 。

Translated by vincent163