BUAA大一下数据结构题解（连续线段）

线段）"/>

BUAA大一下数据结构题解（连续线段）

笔者的一些话：从这里开始，北航数据结构的学习算是正式开始了，链表的知识是十分重要的，是整个数据结构学习的基础，我在学习的时候，一开始没有将链表学的很扎实，觉得使用数组也是可以完成很多操作，但是到后面数组的使用就越来越困难，我也走了很多的弯路，因此恶补了链表的知识。希望学弟学妹们不要偷懒，学好数据结构，从学好链表开始！

【问题描述】
平面上两个点（一个点由(x,y)坐标组成）可构成一个线段，两个线段如果有一个端点相同，则可构成一个连续线段。假设构成线段的两个端点为v1(x1,y1)和v2(x2,y2)，在此满足x1<x2，其中v1称为线段的起点，v2为线段的终点。同样，对于连续线段来说，在此满足xi<xi+1（i=1...n-1，n为连续线段中的端点数，xi为相应端点的X轴坐标）。输入一组线段（用两个端点的x、y坐标表示线段，线段个数大于等于2，小于等于100），编程计算出连续线段中包含最多线段数的线段，输出相应的线段数和起点位置（注意，不是最长的连续线段，是包含最多线段的连续线段）。例如：

上图中有10个线段，其中5、10、4号线段连成了一条连续线段，线段数3条，起点位置为5号线段的左端点；6、8、2、3、9号线段连成了另一条连续线段，该连续线段包含的线段数最多，为5条，起点位置是6号线段的左端点。
注意：
1）不考虑线段中间相交的情况；
2）不会有三条或三条以上的线段共一个端点；
3）只会出现一条包含最多线段的连续线段；

【输入形式】
先从控制台输入线段数，然后从下一行开始分行输入各线段两个端点的x、y坐标，其中第一个端点的X轴坐标小于第二个端点的X轴坐标，即x1<x2，x、y坐标都用整数表示，不会超过int的表示范围。各整数坐标值间以一个空格分隔。
【输出形式】
先在控制台输出包含最多线段数的连续线段的线段数，然后输出连续线段的起点的x、y坐标，输出数据都以一个空格分隔。
【样例输入】

10

80 75 125 75

60 40 80 55

80 55 90 20

140 120 195 205

10 111 70 165

22 35 43 43

22 175 80 205

43 43 60 40

90 20 125 60

70 165 140 120

【样例输出】
5 22 35
【样例说明】
输入了十个线段，第一个线段两个端点分别为(80,75）和(125,75），其它线段类似，如上图所示，这些线段所构成的连续线段中包含最多线段数的连续线段的线段数为5，起点为(22,35），所以输出：5 22 35。
【评分标准】
通过所有测试点将得满分。提交程序名为line.c。

解题思路：首先将线段根据左端点的大小进行排序，然后在以每一个线段为起始线段，向右进行连接，找到以每一个线段为起始线段的包含最多条数线段的线段，然后保存其中最长的就ok了！

参考代码：

#include <stdio.h>
struct point
{int a[2];int b[2];
}point[200],temp;
int arr[200];
int main()
{int n,i,j,l,k,max=0,c,d,flag=0;scanf("%d",&n);for(i=0;i<n;i++)scanf("%d%d%d%d",&point[i].a[0],&point[i].a[1],&point[i].b[0],&point[i].b[1]);//读入端点信息for(i=0;i<n;i++){flag=0;for(j=i+1;j<n;j++){if(point[j].a[0]<point[i].a[0]){temp=point[j];point[j]=point[i];point[i]=temp;flag=1;}}if(flag==0)break;}//将线段按照前端点的大小从左到右排列起来for(i=0;i<n;i++)//每一次遍历都相当于找到以这条线段为起点的最长的线段{l=1;//l代表线段长度k=i;//k代表当前线段位置for(j=i+1;j<n;j++){if(point[j].a[0]==point[k].b[0]&&point[j].a[1]==point[k].b[1]){l++;k=j;}}//从左到右遍历线段，观察是否有重合的端点if(l>max){max=l;c=point[i].a[0];d=point[i].a[1];}//如果这条线段更长就更新}printf("%d %d %d",max,c,d);//输出数据
}