連續線段

• 題目描述
• 題目分析
• 實現思路
• 代碼實現

題目描述

平面上兩個點（一個點由(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坐標，輸出數據都以一個空格分隔。
【樣例輸入】

1080 75 125 7560 40 80 5580 55 90 20140 120 195 20510 111 70 16522 35 43 4322 175 80 20543 43 60 4090 20 125 6070 165 140 120

【樣例輸出】

5 22 35

【樣例說明】
輸入了十個線段，第一個線段兩個端點分別為(80,75）和(125,75），其它線段類似，如上圖所示，這些線段所構成的連續線段中包含最多線段數的連續線段的線段數為5，起點為(22,35），所以輸出：5 22 35。

題目分析

實現思路

存儲輸入線段個數、坐標信息

從輸入線段起終點坐標，尋找連續線段的起點，存儲

根據起點坐標，尋找連續線段的終點坐標，并為每條連續線段的線段個數計數，存儲

根據存儲的每條線段個數，尋找包含最多線段的連續線段

打印結果

代碼實現

#include <stdio.h> #include <string.h>struct L { //線段int x1; //起點int y1;int x2; //終點int y2;int num; //線段個數 };int main() {int i = 0, j = 0, n = 0, k = 0, isl = 0, max = 0, res = 0; // n為線段個數，isl判斷中間點坐標，max最大長度，返回第res+1的連續線段int Ps[100][4];struct L arr[100];//輸入信息，存儲坐標存儲while (n < 2 || n > 100){ //2<=n<=100scanf("%d", &n); //線段個數}for (i = 0; i < n; i++){while (Ps[i][0] >= Ps[i][2]){ //x1<x2scanf("%d%d%d%d", &Ps[i][0], &Ps[i][1], &Ps[i][2], &Ps[i][3]);}}//找起點for (i = 0; i < n; i++){for (j = 0; j < n; j++){if (i == j)continue;if (Ps[i][0] == Ps[j][2] && Ps[i][1] == Ps[j][3]){isl = 1;break;}}if (isl == 0){arr[k].x1 = Ps[i][0];arr[k].y1 = Ps[i][1];arr[k].x2 = Ps[i][2];arr[k].y2 = Ps[i][3];k++;}isl = 0;}//找終點for (i = 0; i < k; i++){arr[i].num = 1;for (j = 0; j < n; j++){if (arr[i].x2 == Ps[j][0] && arr[i].y2 == Ps[j][1]){arr[i].x2 = Ps[j][2];arr[i].y2 = Ps[j][3];arr[i].num++;j = -1;}}}//找最長for (i = 0; i < k; i++){if (max < arr[i].num){max = arr[i].num;res = i;}}printf("%d %d %d\n", arr[res].num, arr[res].x1, arr[res].y1);return 0; }

總結

以上是生活随笔為你收集整理的数据结构-连续线段-C语言-[输入n条线段各个端点坐标，求包含最多线段的连续线段]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。