bzoj#P4225. [POI2010] LAT-Lamp
[POI2010] LAT-Lamp
题目描述
一天,缺德的 Bitratio 打开了 Byteasar 所居住的大楼处的灯光。
Byteasar 无法入睡的时候,缺德的 他开始想知道他的邻居是否也遭受了类似的折磨,也就是说,光线是否也照在他们的窗户上。
已知这个世界归牛顿管理。也就是说,光沿着光线传播,如果光线击中窗口,就会被反射。且根据反射定律,光线的反射角等于入射角。
缺德的 Bitratio 所住的大楼与 Byteasar 的大楼相距 。它们的墙壁都是平行的,光线只在任何窗户的内部反射,反之,它在窗口的边界上被吸收。
我们以以下方式在这两栋建筑的墙上引入坐标系:两个轴都是水平的,而两个轴是垂直的;两个墙上的轴线方向相同,墙的点彼此相对。窗户(在任何一栋建筑上)都是简单的矩形,侧面平行于坐标系的轴。在每栋建筑中,没有两扇窗户共享其内部的任何部分。该灯位于建筑物的墙上,该点既不在任何窗户的内部,也不在任何窗口的边界。
输入部分
第一行为两个整数 , ,分别表示第一栋和第二栋建筑中的窗户数量。
之后 行,描述了 Byteasar 与 Bitratio 的大楼中窗户的位置。
每行包含四个整数 , , , ,表示窗户左上角和右下角的坐标。
输出部分
两行,第一行表示 Byteasar 的大楼中被照射到的窗户的数量 ,第二行输出 个整数,表示被照射到的窗户的编号。
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
数据规模与约定
对于 的数据,,。