题目：
分析：并查集。这题有两个关键点。
第一点：如何判断两条线段是否有交点。
第二点：快速查找某条线段所在集合里的线段条数，用并查集实现。
线段A(x1,y1)-B(x2,y2),所在直线L1方程为F1(x,y)=0;
线段C(x3,y3)-D(x4,y4),所在直线L2方程为F2(x,y)=0;如何判断两条线段有交点：(A,B在直线L2两侧) AND (C,D在直线L1两侧)。
用数学表达式来表示可以这样来表示：F2(x1,y1)*F2(x2,y2) >= 0 AND F1(x3,y3)*F1(x4,y4)>= 0; 等于0表示恰好在直线上。
做这道题，可以先求出F函数，每读入一条新线段，将它和先前的每一条线段作比较，判断是否有交点，有交点，则这两条线段对应的标号相连，进行合并操作merge，每次合并，修改根节点记录的信息。这里并查集考察点：查找某一集合的元素个数。
代码 #include < stdio.h > #include < stdlib.h > #define NN 1004 typedef struct node{ double x, y;}NODE;NODE stap[NN], endp[NN]; // 分别代表起点集和终点集 int index; int cnt[NN], bin[NN], rank[NN]; /* 查找函数+路径压缩 */ int Find( int x){ if (x != bin[x]){ return bin[x] = Find(bin[x]); } return bin[x];} /* 按秩合并，并由根节点记录所代表集合元素个数 */ void Merge( int x, int y){ int fx = Find(x); int fy = Find(y); if (fx != fy){ if (rank[fx] > rank[fy]){ bin[fy] = fx; cnt[fx] += cnt[fy]; } else { if (rank[fy] == rank[fx]){ rank[fy] ++ ; } bin[fx] = fy; cnt[fy] += cnt[fx]; } }} /* 判断t点在线段s1-e1的哪一侧 */ int Value(NODE s1, NODE e1, NODE t){ double ans = (s1.y - e1.y) * (t.x - s1.x) + (s1.x - e1.x) * (s1.y - t.y); if (ans < 0 ){ return - 1 ; } else if (ans > 0 ){ return 1 ; } else { return 0 ; }} /* 判断线段s1-e1和s2-e2是否有交点或是否交叉 */ int Cross(NODE s1, NODE e1, NODE s2, NODE e2){ if ( ! (Value(s1, e1, s2) * Value(s1, e1, e2) > 0 ) && ! (Value(s2, e2, s1) * Value(s2, e2, e1) > 0 )){ return 1 ; } return 0 ;} /* 增加一条线段，同时增加了很多边 */ void Add(NODE s, NODE e){ int i; for (i = 1 ; i < index; i ++ ){ if (Cross(s, e, stap[i], endp[i])){ Merge(i, index); } }} int main(){ int T, x, fx, n, i; char ch[ 4 ]; scanf( " %d " , & T); while (T -- ){ scanf( " %d " , & n); index = 1 ; for (i = 1 ; i <= n; i ++ ){ bin[i] = i; rank[i] = 0 ; cnt[i] = 1 ; } while (n -- ){ scanf( " %s " , ch); if (ch[ 0 ] == ' P ' ){ scanf( " %lf%lf%lf%lf " , & stap[index].x, & stap[index].y, & endp[index].x, & endp[index].y); Add(stap[index], endp[index]); index ++ ; } else { scanf( " %d " , & x); fx = Find(x); printf( " %d\n " , cnt[fx]); } } if (T){ puts( "" ); } } // system("pause"); return 0 ;}