HDU 1558 Segment set（并查集）

题意：

　　给你一些线段的起点和终点的坐标，最后问和某个线段相连的或者间接相连的线段有多少个（包括本身）？

　　P X1 Y1X2 Y2 起点（X1,X2）终点（X2,Y2）；按照出现次数依次编号为1,2,3,4......

　　Q N 问和第N个线段相交或者间接相交的线段有多少个，所谓间接相交就是如果 1 和 2相交， 2 和 3相交那么 1 和 3 就是间接相交。。。。。

解题思路：

　　每给出一个线段就和之前的所有线段判断是否相交，如果相交就合并，最后利用路径压缩后所有节点的父节点都是根节点的特征，找出与所问的这条线段相交的数量（包括本身）。记得最后那个换行在每个样列之间。。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <cmath>
  6 #include <cctype>
  7 #include <algorithm>
  8 #define        EPS .1e-6
  9 using namespace std;
 10 const int MAXN = 1e3 + 3;
 11 int pre[MAXN];
 12 
 13 struct TPoint   //代表一个点
 14 {
 15     float x,y; //横纵坐标
 16 };
 17 
 18 struct TLineSeg   //一条线段
 19 {
 20     TPoint a,b;   //起点和终点
 21 };
 22 
 23 float multiply(TPoint p1,TPoint p2,TPoint p0)
 24 {
 25     return((p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y));
 26 }
 27 
 28 int intersect(TLineSeg u,TLineSeg v) //判断两条是否相交
 29 {
 30     return( (max(u.a.x,u.b.x) >= min(v.a.x,v.b.x))&&(max(v.a.x,v.b.x) >= min(u.a.x,u.b.x))&& (max(u.a.y,u.b.y)>= min(v.a.y,v.b.y))&&  (max(v.a.y,v.b.y)>= min(u.a.y,u.b.y))&& (multiply(v.a,u.b,u.a)*multiply(u.b,v.b,u.a)>=0)&&(multiply(u.a,v.b,v.a)*multiply(v.b,u.b,v.a)>=0));
 31 
 32 }
 33 
 34 int Find(int x)
 35 {
 36     int r = x;
 37     while(pre[r] != r)
 38     {
 39         r = pre[r];
 40     }
 41     int i = x,j;
 42     while(pre[i] != r)
 43     {
 44         j = i;
 45         i = pre[i];
 46         pre[j] = r;
 47     }
 48     return r;
 49 }
 50 
 51 void Mix(int a,int b)
 52 {
 53     int x = Find(a);
 54     int y = Find(b);
 55     if(x > y)
 56     {
 57         pre[x] = y;
 58     }
 59     if(x < y)
 60     {
 61         pre[y] = x;
 62     }
 63 }
 64 
 65 
 66 void Mst()
 67 {
 68     for(int i = 1; i <= MAXN; i++)
 69     {
 70         pre[i] = i;
 71     }
 72 }
 73 int main()
 74 {
 75     int T;
 76     //freopen("in.txt","r",stdin);
 77    // freopen("out.txt","w",stdout);
 78     scanf("%d", &T);
 79     while(T--)
 80     {
 81         Mst();
 82         int N;
 83         scanf("%d", &N);
 84         struct TLineSeg S[MAXN];
 85         memset(S,0,sizeof(S));
 86         int len = 1;
 87         while(N--)
 88         {
 89             char s[3] = {0};
 90             scanf("%s",s);
 91             if(s[0] == 'P')
 92             {
 93                 scanf("%f%f%f%f",&S[len].a.x,&S[len].a.y,&S[len].b.x,&S[len].b.y);
 94                 if(len >= 2)    
 95                 {
 96                     for(int i = 1; i <len; i++) 
 97                     {
 98                         if(intersect(S[len],S[i]))      //如果相交就合并
 99                         {
100                             Mix(i,len);
101                         }
102                     }
103                 }
104                 len++;
105             }
106             if(s[0] == 'Q')
107             {
108                 int num;
109                 scanf("%d",&num);
110                 for(int i = 1;i <= len; i++)
111                     Find(i);
112                 int ans = 0;
113                 for(int i = 1; i <= len ;i++)    //统计和这条线段相连的有多少个（包括本身）
114                     if(pre[i] == pre[num])
115                         ans++;
116                 printf("%d
",ans);
117             }
118         }
119         if(T)     //记得最后有一个换行，记得最后有一个换行，记得最后有一个换行！！！！！！
120             cout <<endl;
121     }
122     return 0;
123 }

It's not numeral,character and punctuation .It's my life.