编程介的小学生 2019-09-14 21:44 采纳率: 20.5%
浏览 158

线段处理 算法程序的实现

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

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥30 帮我写一段可以读取LD2450数据并计算距离的Arduino代码
    • ¥15 C#调用python代码(python带有库)
    • ¥15 矩阵加法的规则是两个矩阵中对应位置的数的绝对值进行加和
    • ¥15 活动选择题。最多可以参加几个项目?
    • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
    • ¥15 vs2019中数据导出问题
    • ¥20 云服务Linux系统TCP-MSS值修改?
    • ¥20 关于#单片机#的问题:项目:使用模拟iic与ov2640通讯环境:F407问题:读取的ID号总是0xff,自己调了调发现在读从机数据时,SDA线上并未有信号变化(语言-c语言)
    • ¥20 怎么在stm32门禁成品上增加查询记录功能
    • ¥15 Source insight编写代码后使用CCS5.2版本import之后,代码跳到注释行里面