线段 的计算问题

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,表示满足条件的线段对的个数。
Sample Input

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
Sample Output

3
10

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问

相似问题

3
用Python,已知两条线段的顶点坐标,求两条线的夹角
1
Galou is back! 类欧几里得算法 线段树方面的一个问题的思路求教,怎么利用C语言的编写实现
0
区间线段数组搜索数据结构方面的问题,如何利用C语言进行计算的
0
线段树的搜索和遍历,线段树相关问题的解决,使用C语言的办法
0
整数线段树规划的问题,如何利用C语言编程解决实现
0
一个时间方面的区间线段的问题的办法,怎么解决这个问题用到C语言的办法
0
二进制线段数列的枚举的典型问题,使用C语言编写程序设计解决这个算法是怎么做的
1
有没有大佬讲一手线段树的区间更新,初学,实在不懂
0
线段与圆求交点,所求交点不在圆上,但是在直线上,不知为何?
0
区域线段的算法的问题的一种题目,怎么利用C语言的程序的编写的技巧来实现?
0
圆周上交叉的线段的结点的问题,怎么利用C语言的程序的编写的实现的思路?
0
算法问题用线段如何构成三角形,怎么利用C语言的程序的代码的编制实现程序?
1
Qt Qchart绘制的曲线怎么在鼠标点击时添加2条竖分割线来选取线段
0
线段在圆周上交叉点的问题,怎么才能使用C语言的编写程序的知识的办法去实现的呢?
0
计算图中的沟渠与沟渠之间是否有相交,运用C语言程序编写代码的思路怎么才能实现的
1
圆圈和线段在坐标系上的计算,怎么采用C语言的程序的代码的编写的功能加以实现?
0
区间线段的搜索问题的综合运用,怎么使用C语言的程序编写的程序的格式来实现算法的解答
0
三维坐标的点的集合构成的线段计算,怎么运用 C 语言的程序代码编写的思想的方式去实现的呢?
0
圆和直线线段的焦点和相切,怎么使用C语言的程序的代码编写的办法有效地实现的过程是什么
0
计算圆形和线段的切线的问题,要求是使用C语言的程序的代码设计的编写的过程如何加以实现的呢