bzoj#P4225. [POI2010] LAT-Lamp

[POI2010] LAT-Lamp

题目描述

一天,缺德的 Bitratio 打开了 Byteasar 所居住的大楼处的灯光。

Byteasar 无法入睡的时候,缺德的 他开始想知道他的邻居是否也遭受了类似的折磨,也就是说,光线是否也照在他们的窗户上。

已知这个世界归牛顿管理。也就是说,光沿着光线传播,如果光线击中窗口,就会被反射。且根据反射定律,光线的反射角等于入射角。

缺德的 Bitratio 所住的大楼与 Byteasar 的大楼相距 10m10m 。它们的墙壁都是平行的,光线只在任何窗户的内部反射,反之,它在窗口的边界上被吸收。

我们以以下方式在这两栋建筑的墙上引入坐标系:两个轴都是水平的,而两个轴是垂直的;两个墙上的轴线方向相同,墙的点彼此相对。窗户(在任何一栋建筑上)都是简单的矩形,侧面平行于坐标系的轴。在每栋建筑中,没有两扇窗户共享其内部的任何部分。该灯位于建筑物的墙上,该点既不在任何窗户的内部,也不在任何窗口的边界。

输入部分

第一行为两个整数 nn , mm ,分别表示第一栋和第二栋建筑中的窗户数量。

之后 n+mn+m 行,描述了 Byteasar 与 Bitratio 的大楼中窗户的位置。

每行包含四个整数 x1x_1 , y1y_1 , x2x_2 , y2y_2 ,表示窗户左上角和右下角的坐标。

输出部分

两行,第一行表示 Byteasar 的大楼中被照射到的窗户的数量 kk ,第二行输出 kk 个整数,表示被照射到的窗户的编号。

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

数据规模与约定

对于 100%100\% 的数据,1000x1,i<x2,i1000-1000 \le x_{1,i} \lt x_{2,i} \le 10000y1,i<y2,i10000 \le y_{1,i} < y_{2,i} \le 1000