切割矩形

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18: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