poj 1127（直线相交+并查集）

Jack Straws

Description

In the game of Jack Straws, a number of plastic or wooden "straws" are dumped on the table and players try to remove them one-by-one without disturbing the other straws. Here, we are only concerned with if various pairs of straws are connected by a path of touching straws. You will be given a list of the endpoints for some straws (as if they were dumped on a large piece of graph paper) and then will be asked if various pairs of straws are connected. Note that touching is connecting, but also two straws can be connected indirectly via other connected straws.

Input

Input consist multiple case,each case consists of multiple lines. The first line will be an integer n (1 < n < 13) giving the number of straws on the table. Each of the next n lines contain 4 positive integers,x1,y1,x2 and y2, giving the coordinates, (x1,y1),(x2,y2) of the endpoints of a single straw. All coordinates will be less than 100. (Note that the straws will be of varying lengths.) The first straw entered will be known as straw #1, the second as straw #2, and so on. The remaining lines of the current case(except for the final line) will each contain two positive integers, a and b, both between 1 and n, inclusive. You are to determine if straw a can be connected to straw b. When a = 0 = b, the current case is terminated.

When n=0,the input is terminated.

There will be no illegal input and there are no zero-length straws.

Output

You should generate a line of output for each line containing a pair a and b, except the final line where a = 0 = b. The line should say simply "CONNECTED", if straw a is connected to straw b, or "NOT CONNECTED", if straw a is not connected to straw b. For our purposes, a straw is considered connected to itself.

Sample Input

1 6 3 3

4 6 4 9

4 5 6 7

1 4 3 5

3 5 5 5

5 2 6 3

5 4 7 2

1 4

1 6

3 3

6 7

2 3

1 3

0 0

0 2 0 0

0 0 0 1

1 1

2 2

1 2

0 0

Sample Output

CONNECTED

NOT CONNECTED

CONNECTED

NOT CONNECTED

CONNECTED

判断直线相交利用徐本柱教授的跨立方法求解：

跨立的含义是：如果一条线段的一个端点在一条直线的一边，另一个端点在这条直线的另一端，我们就说这条线段跨立在这条直线上。显然，如果两条线段互相跨立，那它们一定是相交的。当然还有一些边值情况，也就是说有可能线段的端点在另一条线段所在的直线上。

线段相交满足且只需满足如下两个条件就可以了：
1 两条线段相互跨立；

2 一条线段的一个端点在另一条线段上。（这是针对边值情况而言的）
我们进一点来说明一下如何知道，一条线段是跨立在另一条线段上的。

如左图所示，线段向量 P1P2 是跨立在 P3P4 上的。我们取端点 P3 为虚线所示向量的起点，P1 和 P2 为终点，则向量组 P3P1、P3P4 和向量组 P3P2、P3P4 的叉积符号是相反的，因为由 P3P1 转向 P3P4 为顺时针，而由 P3P2 转向 P3P4 则为逆时针。同样的，也可以判断出 P3P4 是跨立在 P1P2 上的。这样我们就可以知道，两条线段是相交的。再看一看右图，按照跨立的方法，很容易知道，这两条线段是不相交的。

用跨立判断是否相交，相交用并查集连通处理。

最后读入棍子序号直接判断是不是双方都有一样的爸爸→_→。

下面给出代码:

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<cstring>
  4 #include<algorithm>
  5 #define clr(x) memset(x,0,sizeof(x))
  6 #define LL long long
  7 using namespace std;
  8 struct point
  9 {
 10     LL x,y;
 11     point operator + (point b)
 12     {
 13         b.x=b.x+x;
 14         b.y=b.y+y;
 15         return b;
 16     }
 17     point operator - (point b)
 18     {
 19         b.x=x-b.x;
 20         b.y=y-b.y;
 21         return b;
 22     }
 23     point operator *(point b)
 24     {
 25         b.x=x*b.x;
 26         b.y=y*b.y;
 27         return b;
 28     }
 29     LL dot(point b)//点积
 30     {
 31         return x*b.x+y*b.y;
 32     }
 33     LL  det(point b)//叉积
 34     {
 35         return x*b.y-y*b.x;
 36     }
 37 }u,v;
 38 struct line
 39 {
 40     point pt1,pt2;
 41 }a[1000];
 42 int fa[1000];
 43 void done(int n);
 44 void Union(int a,int b);
 45 int Find(int x);
 46 bool infer(line a,line b);
 47 LL onseg(point p,point p1,point p2);
 48 int main()
 49 {
 50     int n;
 51     while(scanf("%d",&n) && n!=0)
 52     {
 53         done(n);
 54     }
 55     return 0;
 56 }
 57 void done(int n)
 58 {
 59     clr(fa);
 60     for(int i=1;i<=n;i++)
 61         fa[i]=i;
 62     clr(a);
 63     for(int i=1;i<=n;i++)
 64     {
 65         scanf("%lld%lld%lld%lld",&a[i].pt1.x,&a[i].pt1.y,&a[i].pt2.x,&a[i].pt2.y);
 66         if(a[i].pt1.x>a[i].pt2.x)
 67             swap(a[i].pt1,a[i].pt2);
 68     }
 69     for(int i=1;i<=n;i++)
 70         for(int j=i+1;j<=n;j++)
 71         if(infer(a[i],a[j]))
 72         {
 73             Union(i,j);
 74         }
 75     int a,b;
 76     while(scanf("%d%d",&a,&b) && a && b)
 77     {
 78         if(Find(a)==Find(b))
 79             printf("CONNECTED
");
 80         else
 81             printf("NOT CONNECTED
");
 82     }
 83     return ;
 84 }
 85 void Union(int a,int b)
 86 {
 87     if(Find(a)!=Find(b))
 88         fa[Find(a)]=Find(b);
 89     return ;
 90 
 91 }
 92 int Find(int x)
 93 {
 94     if(fa[x]==x)
 95         return x;
 96     return fa[x]=Find(fa[x]);
 97 }
 98 bool infer(line a,line b)//判断是否相交
 99 {
100     if(a.pt2.x<b.pt1.x)//快速处理，若两条直线x部分或y部分不重叠，则肯定不相交。
101         return 0;
102     if(a.pt1.y>a.pt2.y)
103         swap(a.pt1,a.pt2);
104     if(b.pt1.y>b.pt2.y)
105         swap(b.pt1,b.pt2);
106     if(a.pt2.y<b.pt1.y)
107         return 0;
108     if((b.pt1-b.pt2).det(a.pt1-b.pt2)*(b.pt1-b.pt2).det(a.pt2-b.pt2)<0 && (a.pt2-a.pt1).det(b.pt1-a.pt1)*(a.pt2-a.pt1).det(b.pt2-a.pt1)<0) return 1;
109 //判断叉积符号是否相反，若相反则相交。
110 //判断叉积=0的情况。
111     if((b.pt1-b.pt2).det(a.pt1-b.pt2)==0 && onseg(a.pt1,b.pt1,b.pt2)) return 1;
112     if((b.pt1-b.pt2).det(a.pt2-b.pt2)==0 && onseg(a.pt2,b.pt1,b.pt2)) return 1;
113     if((a.pt2-a.pt1).det(b.pt1-a.pt1)==0 && onseg(b.pt1,a.pt1,a.pt2)) return 1;
114     if((a.pt2-a.pt1).det(b.pt2-a.pt1)==0 && onseg(b.pt2,a.pt1,a.pt2)) return 1;
115 //若均不符合上述相交情况，则不相交。
116     return 0;
117 }
118 LL onseg(point p,point p1,point p2)//判断p是否在p1,p2上。
119 {
120     if(p1.x>p2.x)
121         swap(p1,p2);
122     if(p.x<p1.x || p.x>p2.x) return 0;
123     if(p1.y>p2.y)
124         swap(p1,p2);
125     if(p.y<p1.y || p.y>p2.y) return 0;
126     return 1;
127 }