poj 1127Jack Straws解题报告

并查集+线段相交，除了混了一下，没什么难度
View Code
 1 #include<stdio.h>
 2 #include<string.h>
 3 #define N 20
 4 #define min(x,y) (x<y?x:y)
 5 #define max(x,y) (x>y?x:y)
 6 int f[N];
 7 int n;
 8 struct point
 9 {
10     int x,y;
11 };
12 struct segment
13 {
14     point p1,p2;
15 };
16 segment s[N];
17 void init()
18 {
19     int i;
20     for(i=1;i<=n;i++)
21     f[i]=i;
22 }
23 int find(int i)
24 {
25     int r=i;
26     while(r!=f[r])
27     r=f[r];
28     int t;
29     while(i!=f[i])
30     {
31         t=f[i];
32         f[i]=r;
33         i=t;
34     }
35     return r;
36 }
37 void uni(int i,int j)
38 {
39     int t1=find(i);
40     int t2=find(j);
41     if(t1^t2)
42     f[t2]=t1;
43 }
44 int mul(point p1,point p2,point p3)
45 {
46     return (p2.x-p1.x)*(p3.y-p2.y)-(p3.x-p2.x)*(p2.y-p1.y);
47 }
48 bool cross(segment s1,segment s2)//线段是否相交
49 {
50     if(min(s1.p1.x,s1.p2.x)>max(s2.p1.x,s2.p2.x)||max(s1.p1.x,s1.p2.x)<min(s2.p1.x,s2.p2.x))
51     return false;
52     if(min(s1.p1.y,s1.p2.y)>max(s2.p1.y,s2.p2.y)||max(s1.p1.y,s1.p2.y)<min(s2.p1.y,s2.p2.y))
53     return false;
54     if(mul(s1.p1,s1.p2,s2.p1)*mul(s1.p1,s1.p2,s2.p2)<=0&&mul(s2.p1,s2.p2,s1.p1)*mul(s2.p1,s2.p2,s1.p2)<=0)
55     return true;
56     return false;
57 }
58 int main()
59 {
60     int a,b;
61     int i,j;
62     while(scanf("%d",&n)&&n)
63     {
64         init();
65         for(i=1;i<=n;i++)
66         scanf("%d%d%d%d",&s[i].p1.x,&s[i].p1.y,&s[i].p2.x,&s[i].p2.y);
67         for(i=1;i<=n;i++)
68         for(j=1;j<=n;j++)
69         {
70             if(i==j)
71             continue;
72             if(cross(s[i],s[j]))
73             uni(i,j);
74         }
75         while(scanf("%d%d",&a,&b)&&(a||b))
76         {
77             if(find(a)^find(b))
78             printf("NOT CONNECTED\n");
79             else
80             printf("CONNECTED\n");
81         }
82     }
83     return 0;
84 }