poj 1127:Jack Straws（判断两线段相交 + 并查集）

 1 int UFS_NUM;    //并查集中元素总数 
 2 typedef struct node{
 3     int data;    //节点对应的编号 
 4     int rank;    //节点对应秩 
 5     int parent;    //节点对应的双亲下标 
 6 }UFSTree;        //并查集树的节点类型 
 7 void MAKE_SET(UFSTree t[])    //初始化并查集树 
 8 {
 9     int i;
10     for(i=1;i<=UFS_NUM;i++){
11         t[i].data = i;        //数据为该点编号 
12         t[i].rank = 0;        //秩初始化为0 
13         t[i].parent = i;    //双亲初始化为指向自己 
14     }
15 }
16 int FIND_SET(UFSTree t[],int x)    //在x所在的子树中查找集合编号
17 {
18     if(t[x].parent == x)    //双亲是自己 
19         return x;    //双亲是自己，返回 x 
20     else    //双亲不是自己 
21         return FIND_SET(t,t[x].parent);    //递归在双亲中查找x 
22 } 
23 void UNION(UFSTree t[],int x,int y)    //将x和y所在的子树合并
24 {
25     x = FIND_SET(t,x);    //查找 x 所在分离集合树的编号 
26     y = FIND_SET(t,y);    //查找 y 所在分离集合树的编号 
27     if(t[x].rank > t[y].rank)    //y 节点的秩小于 x节点的秩 
28         t[y].parent = x;        //将 y 连接到 x 节点上，x 作为 y 的双亲节点 
29     else{                //y 节点的秩大于等于 x 节点的秩 
30         t[x].parent = y;            //将 x 连接到 y 节点上，y 作为 x 的双亲节点 
31         if(t[x].rank==t[y].rank)    //x 和 y的双亲节点秩相同 
32             t[y].rank++;            //y 节点的秩增 1 
33     }
34 } 

 1 #include <iostream>
 2 using namespace std;
 3 /*--------- 并查集 模板 ------------*/
 4 int UFS_NUM;    //并查集中元素总数 
 5 typedef struct node{
 6     int data;    //节点对应的编号 
 7     int rank;    //节点对应秩 
 8     int parent;    //节点对应的双亲下标 
 9 }UFSTree;        //并查集树的节点类型 
10 void MAKE_SET(UFSTree t[])    //初始化并查集树 
11 {
12     int i;
13     for(i=1;i<=UFS_NUM;i++){
14         t[i].data = i;
15         t[i].rank = 0;
16         t[i].parent = i;
17     }
18 }
19 int FIND_SET(UFSTree t[],int x)    //在x所在的子树中查找集合编号
20 {
21     if(t[x].parent == x)
22         return x;
23     else 
24         return FIND_SET(t,t[x].parent);
25 } 
26 void UNION(UFSTree t[],int x,int y)    //将x和y所在的子树合并
27 {
28     x = FIND_SET(t,x);
29     y = FIND_SET(t,y);
30     if(t[x].rank > t[y].rank)
31         t[y].parent = x;
32     else{
33         t[x].parent = y;
34         if(t[x].rank==t[y].rank)
35             t[y].rank++;
36     }
37 } 
38 
39 /*--------- 判断两线段相交 模板 ------------*/ 
40 const double eps=1e-10;
41 struct point { double x, y; };
42 double min(double a, double b) { return a < b ? a : b; }
43 double max(double a, double b) { return a > b ? a : b; }
44 bool inter(point a, point b, point c, point d){
45 if ( min(a.x, b.x) > max(c.x, d.x) ||
46 min(a.y, b.y) > max(c.y, d.y) ||
47 min(c.x, d.x) > max(a.x, b.x) ||
48 min(c.y, d.y) > max(a.y, b.y) ) return 0;
49 double h, i, j, k;
50 h = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
51 i = (b.x - a.x) * (d.y - a.y) - (b.y - a.y) * (d.x - a.x);
52 j = (d.x - c.x) * (a.y - c.y) - (d.y - c.y) * (a.x - c.x);
53 k = (d.x - c.x) * (b.y - c.y) - (d.y - c.y) * (b.x - c.x);
54 return h * i <= eps && j * k <= eps;
55 }
56 
57 /*---------- 代码实现 -----------*/ 
58 struct line
59 {
60     point p1;
61     point p2;
62 };
63 int main()
64 {
65     int n;
66     UFSTree t[105]; 
67     while(cin>>n){
68         if(n==0) break;
69         UFS_NUM = n;//确定并查集树中元素总数 
70         MAKE_SET(t);    //初始化并查集 
71         line l[15];
72         for(int i=1;i<=n;i++)
73             cin>>l[i].p1.x>>l[i].p1.y>>l[i].p2.x>>l[i].p2.y;
74         for(int i=1;i<=n;i++)    //根据关系生成关系树 
75             for(int j=1;j<=n;j++){
76                 if(i==j) continue;
77                 if(inter(l[i].p1,l[i].p2,l[j].p1,l[j].p2)){    //如果相交，有亲戚关系 
78                     UNION(t,i,j);    //合并相关集合 
79                 }
80             }
81         int l1,l2;
82         while(cin>>l1>>l2){
83             if(l1==0 && l2==0)
84                 break;
85             l1 = FIND_SET(t,l1);
86             l2 = FIND_SET(t,l2);
87             if(l1 == l2)
88                 cout<<"CONNECTED"<<endl;
89             else
90                 cout<<"NOT CONNECTED"<<endl;
91         }
92     }
93     return 0;
94 }