#P50581. 「POI2010」灯 Lamp
「POI2010」灯 Lamp
题目描述
译自 POI 2010 Stage 3. Day 1「Lamp」
在夜深人静的夜晚里,Bitratio 打开了 Byteasar 所在建筑物门口的灯。灯发出的强光导致 Byteasar 无法睡觉。尽管灯没有直接照在 Byteasar 的窗户上,却通过其他的窗户反射进入了 Byteasar 的卧室。Byteasar 由于无法睡觉而感到烦躁。他很好奇他的邻居是否也受到了同样的干扰,于是他来向你求助。你很了解他,因此你清楚地明白,在写出程序并解出这个问题之前你也无法入眠。
Byteasar 住在建筑物 B 里,有 个窗户。灯在这个建筑物最下方的一个墙上。在建筑物 的对面恰好 米有另一个建筑物 C,且这个建筑物的墙与 B 建筑物的墙平行。
灯光的传播方式与物理学定律一样,遇到窗户时会发生反射。灯光的反射满足反射定律,即入射角等于出射角。
我们以如下方式定义两个建筑物的墙的坐标系统。两个建筑物的 X 轴都是水平的,而 Y 轴都是竖直的。两堵墙的坐标轴方向是相同的,且两堵墙上的 坐标恰好面对面。每一个窗户用坐标系中一个四条边与坐标轴平行的矩形表示。一条光线只在窗户的内部被反射,在窗户的边界上会被吸收。光源在 B 建筑物的原点上,保证该点不在任何一个窗户的边界或内部。
输入格式
第一行有两个整数 ,分别表示第一个建筑物和第二个建筑物的窗口个数。
接下来 行表示 B 建筑的窗户。第 行含有四个整数 ,用空格分隔,表示 B 建筑的第 个窗口是一个矩形,且其左下角坐标为 ,右上角坐标为 。
接下来 行以相同格式表示 C 建筑的窗户。
输出格式
第一行输出 B 建筑中受到光线照射的窗口数量。因为 Byteasar 正在受到强光照射,你可以认为至少有一个这样的窗口。
第二行按从小到大的顺序输出 B 建筑受到光线照射的窗口编号,用空格分隔。
样例
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
2
1 2
一条光线经过 C 建筑的第一个窗口反射后会照射到 B 建筑的第一个窗口(例如光线可能在 位置照射 C 建筑后被反射到 B 建筑的 位置)。要照射到 B 建筑的第二个窗口,这条光线至少要被反射三次。例如,该光线会从 B 建筑反射到 C 建筑的 位置处(在 C 建筑的第二个窗口内),并照射在 B 建筑的 位置处。没有光线会照到 B 建筑的第三个窗口。事实上,C 建筑的每个窗口都被光线照射过,但上图只画出了照射过某个 B 建筑窗口的光线。
数据范围与提示
对于 的数据, 。
Translated by vincent163