2447. sunny的游戏

单点时限: 2.0 sec

内存限制: 256 MB

sunny 最近做了一个小游戏-一些矩形的木板在窗口中随机的移动,每隔一段时间更新一次,每次更新的时候将屏幕上所有产生碰撞的木板都消除掉,只留下没有产生碰撞的木板。

两块木板产生碰撞的条件是:两块木板的重叠面积 >0. 也就是说当两块木板在边界接触的时候不会产生碰撞。木板的边都平行于坐标轴,也就是均为水平或是竖直的。

由于 sunny 没写过游戏,所以想让你帮忙写一个程序 : 给出某一个时刻屏幕上 n 个矩形木板的位置,下一个时刻是游戏更新的时刻,让你求更新结束之后屏幕上还剩下多少个矩形木板 .

输入格式

第一行有一个整数 T, 表示有 T 组测试数据

每组测试数据第一行是一个整数 N( 0<=N<=100 ) 表示屏幕上矩形木板的数量

接下来有 N 行,每行四个整数 x1,y1,x2,y2 ( 0=<x1<x2<=1000 ,0=<y1<y2<=1000) 表示矩形木板的左下角坐标和右上角的坐标,每个数以一个空格间隔。

输出格式

对于每组测试数据输出一个整数 (独占一行),输出更新结束之后屏幕上剩下矩形的数目。

样例

Input
2
3
0 0 10 10
11 11 12 12
3 4 4 5
4
1 1 3 3
2 2 3 10
4 5 10 5
0 0 1 1
Output
1
2

35 人解决,61 人已尝试。

43 份提交通过,共有 161 份提交。

5.2 EMB 奖励。

创建: 15 年,11 月前.

修改: 7 年,3 月前.

最后提交: 1 年,1 月前.

来源: 2008年选拔赛

题目标签