切割矩形

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 cutting.in 输出文件 cutting.out

【问题描述】

有一些实心的矩形，它们的边都平行于平面直角坐标轴，小Bug画了一些平行于X轴的线段，他想知道被这些线段切割到的实心矩形数目，一个实心矩形被一条线段切割到当且仅当它们至少有一个交点，如果一个实心矩形被K条线段切割，将被计算K次。

【输入格式】

输入文件第一行有一个正整数T，T<=20，表示接下来有T个测试数据。
每个测试数据的第一行有一个正整数N，N<=30000，表示实心矩形的数目，接下来有N行，每行有4个非负整数：x1,y1,x2,y2，表示对应矩形的左下角及右上角坐标，满足x1<x2且y1<y2；接下来有一个正整数Q，Q<=30000，表示线段的数目，接下来有Q行，每一行有4个非负整数：x3,y3,x4,y4，分别表示对应线段的两个端点坐标，其中x3<x4且y3=y4。

所有的整数都不超过100000000。



【输出格式】

   对于每个测试数据，输出有一行，包含一个整数，即被这些线段切割到的实心矩形总数。

【输入样例】

cutting.in
1
3
1 1 3 4
2 3 4 5
5 1 6 3
5
0 1 6 1
0 3 6 3
0 5 6 5
0 5 2 5
0 6 2 6

cutting.out
7