#P1834. 线段处理

线段处理

Description

题目描述:

在平面上有许多线段,其中一些平行于y轴且在x轴上的间距相等(均为100),起始y坐标都是0,终止y坐标都是32767,称作第一类线段,把这些线段按照x坐标从小到大编号0,1 … n1-1,第二类线段与y轴不平行,而且起点和终点在不同的两条第一类线段上,两条线段最多有一个交点(没有重合或部分重合的情况),第三类线段是第二类线段被第一类线段切割所成的小线段,如下图:

任务描述: 给出所有线段的描述,求出满足以下条件的第三类线段对的个数:两个线段有在非端点处有交点。

Input

第一行是一个正整数num,表示测试数据的组数,下面是num组测试数据。

每组测试数据的第一行是两个正整数n1, n2表示第一类和第二类线段的个数(2<=n1<=16,0<=n2<32768),下面有n2行,每行描述一条第二类线段,有四个正整数k1 p1 k2 p2,k1和k2分别表示此线段的起点和终点所在的第一类线段的编号,p1和p2分别表示此线段起点和终点的y坐标(0<=p1,p1 < 32768 )。

Output

对每组测试数据输出一行,一个正整数n,表示满足条件的线段对的个数。

2
2 5
0 1 1 4
0 3 1 1
0 4 1 5
0 5 1 4
0 6 1 4
4 8
0 0 2 2
0 1 2 3
0 3 2 1
0 3 3 2
1 0 3 2
1 3 2 0
2 0 3 1
2 3 3 0
3
10

Source

qinlu@POJ