判断线段相交(hdu1558 Segment set 线段相交+并查集)

先说一下题目大意：给定一些线段，这些线段顺序编号，这时候如果两条线段相交，则把他们加入到一个集合中，问给定一个线段序号，求在此集合中有多少条线段。

这个题的难度在于怎么判断线段相交，判断玩相交之后就是怎么找个他们之间的联系，这时候就要用到并查集了。

步骤：

1.判断两条线段相交

2. 用并查集实现查找线段个数和添加到集合中

关于这个判断线段相交的问题。我搞了一晚上加上一下午，刚开始自己想了一种数学上的相交，就是先求出两条线段所在的线性方程，然后求出他们的交点，最后在判断这个交点在不在这两个线段之间。这种方式刚开始一想挺简单的，但是在判断在不在两个线段之间就显得比较麻烦了，而且刚开始还漏了一种情况，就是在他们斜率不存在时怎么求出方程来，当时没有考虑这一点直接wa了，后来又加上了这种情况才AC了。

还有一种方法就是利用向量来判定线段是否相交，这个我是看的算法导论上的，答题思路就是判断其中一条线段是否横跨另一条线段，如果这两条线段都互相横跨另一条，那么一定相交，当然还有边界条件，就是这个交点是边界在线段的终点的情况，那具体怎么判断一条线段是否横跨另外一条线段呢，这时候用到向量了，两个向量p1，p2,如果他们的叉乘积大于0，就说明p1位于p2的逆时针的方向，小于0顺时针，等于0共线。所以这一步很关键。当解决了这个问题之后，那么就好办了，如果一条线段的一个点在顺时针侧，一个点在逆时针侧，那么这条线段横跨另一条直线，注意是直线，还不是线段，如果同时另外一条线段也横跨这一条，那么这时就是两个线段相互横跨了，就是相交了。还有一个关键点就是在边界情况下(就是一条线段的一个端点在另一条线段上的时候)怎么办，这时候用到上面写好的函数来判断，如果返回值是0，那么就是临界条件，这时候判断其中一个端点和另外一条线段的关系就行了，如果都不满足上面的这些情况，肯定是不相交了。

还有一点需要注意，在利用并查集实现的时候，要用两个，一个是普通的并查集来存放它们之间的关系，还有一个是存放它们当前集合的数目。具体代码如下；

代码一(第一种判断线段相交的方式)（后来证明可能有些数据过不了，不建议用这个）

  1 #include<iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #define EPS 1e-8
  5 using namespace std;
  6 const int N = 1005;
  7 struct point{
  8     double x, y;
  9 };
 10 struct segmnt{
 11     point ori, des;
 12 };
 13 int father[N], num[N];//father用来保存相交的线段的集合，num表示当前线段所在集合有多少条线段
 14 segmnt seg[N];
 15 //初始化
 16 void init(int n)
 17 {
 18     
 19     for (int i = 1; i <= n; i++)
 20     {
 21         father[i] = i;
 22         num[i] = 1;
 23     }
 24 }
 25 //判断线段是否相交
 26 bool is_Cross(segmnt s1, segmnt s2)
 27 {
 28     point p1, p2, p3, p4;
 29     p1 = s1.ori; p2 = s1.des;
 30     p3 = s2.ori; p4 = s2.des;
 31     //当第一条线段斜率不存在，第二条斜率存在时
 32     if (p1.x == p2.x && p3.x != p4.x)
 33     {
 34         double k = (p4.y - p3.y) / (p4.x - p3.x);
 35         double y = k * (p1.x - p3.x) + p3.y;
 36         return ((y - p1.y >= EPS && y - p2.y <= EPS) || (y - p1.y <= EPS && y - p2.y >= EPS));
 37     }
 38     //当第一条线段斜率存在，第二条斜率不存在时
 39     else if (p3.x == p4.x && p1.x != p2.x)
 40     {
 41         double k = (p2.y - p1.y) / (p2.x - p1.x);
 42         double y = k * (p3.x - p1.x) + p1.y;
 43         return ((y - p3.y >= EPS && y - p4.y <= EPS) || (y - p3.y <= EPS && y - p4.y >= EPS));
 44     }
 45     //当第一条第二条斜率都不存在时
 46     else if (p1.x == p2.x && p3.x == p4.x)
 47     {
 48         return p1.x == p3.x;
 49     }
 50     //当他们斜率都存在时，先求出方程，然后求出他们的交点，判断交点是否在两条线段上
 51     double k1 = (s1.des.y - s1.ori.y) / (s1.des.x - s1.ori.x);
 52     double k2 = (s2.des.y - s2.ori.y) / (s2.des.x - s2.ori.x);
 53     double x0 = (k1 * s1.ori.x - k2 * s2.ori.x + s2.ori.y - s1.ori.y) / (k1 - k2);
 54     double y0 = k1 * (x0 - s1.ori.x) + s1.ori.y;
 55     if (((x0 >= s1.ori.x && x0 <= s1.des.x) || (x0 >= s1.des.x && x0 <= s1.ori.x)) && ((y0 >= s1.ori.y && y0 <= s1.des.y) || (y0 >= s1.des.y && y0 <= s1.ori.y)) && ((x0 >= s2.ori.x && x0 <= s2.des.x) || (x0 >= s2.des.x && x0 <= s2.ori.x)) && ((y0 >= s2.ori.y && y0 <= s2.des.y) || (y0 >= s2.des.y && y0 <= s2.ori.y)))
 56         return true;
 57     return false;
 58 }
 59 //并查集查找
 60 int find(int x)
 61 {
 62     while (x != father[x])
 63         x = father[x];
 64     return x;
 65 }
 66 //合并
 67 void merge(int a, int b)
 68 {
 69     int ta = find(a);
 70     int tb = find(b);
 71     if (ta != tb)
 72     {
 73         father[ta] = tb;
 74         num[tb] += num[ta];
 75     }
 76 }
 77 int main()
 78 {
 79     int t, n;
 80     scanf("%d", &t);
 81     while (t--)
 82     {
 83         int index = 0;        
 84         scanf("%d", &n);
 85         init(n);
 86         char option;
 87         for (int i = 0; i < n; i++)
 88         {
 89             getchar();
 90             scanf("%c", &option);
 91             if (option == 'P')
 92             {
 93                 ++index;
 94                 scanf("%lf %lf %lf %lf", &seg[index].ori.x, &seg[index].ori.y, &seg[index].des.x, &seg[index].des.y);    
 95                 for (int i = 1; i < index; i++)
 96                     if (is_Cross(seg[i], seg[index]))
 97                         merge(i, index);
 98             }
 99             else
100             {
101                 int k;
102                 scanf("%d", &k);
103                 printf("%d
", num[find(k)]);
104             }
105         }
106         if (t)
107             puts("");
108     }
109     return 0;
110 }

View Code

代码二(第二种判断线段相交方式)

  1 #include<iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 using namespace std;
  5 const int N = 1005;
  6 struct point{
  7     double x, y;
  8 };
  9 int father[N], num[N];//father用来保存相交的线段的集合，num表示当前线段所在集合有多少条线段
 10 point a[N], b[N];//a代表一个线段的起点，b代表终点
 11 //初始化
 12 void init(int n)
 13 {
 14     
 15     for (int i = 1; i <= n; i++)
 16     {
 17         father[i] = i;
 18         num[i] = 1;
 19     }
 20 }
 21 double Min(double a, double b)
 22 {
 23     return a < b ? a : b;
 24 }
 25 double Max(double a, double b)
 26 {
 27     return a > b ? a : b;
 28 }
 29 //用来判断点c在线段ab的哪一侧，如果返回正值就是逆时针那侧，如果是负值就是顺时针那侧
 30 double direction(point a, point b, point c)
 31 {
 32     point t1, t2;
 33     t1.x = c.x - a.x; t1.y = c.y - a.y;
 34     t2.x = b.x - a.x; t2.y = b.y - a.y;
 35     return (t1.x * t2.y - t1.y * t2.x);
 36 }
 37 //前提条件已知ac和ab共线了，判断点c是否在线段ab上，如果是就返回true；
 38 bool onSegment(point a, point b, point c)
 39 {
 40     double minx, miny, maxx, maxy;
 41     minx = Min(a.x, b.x);
 42     maxx = Max(a.x, b.x);
 43     miny = Min(a.y, b.y);
 44     maxy = Max(a.y, b.y);
 45     return (c.x >= minx && c.x <= maxx && c.y >= miny && c.y <= maxy);
 46 }
 47 //判断线段是否相交，线段一是p1p2, 线段二是p3p4,如果相交返回true；
 48 bool segment_intersect(point p1, point p2, point p3, point p4)
 49 {
 50     //判断p1在线段p3p4的哪一侧
 51     double d1 = direction(p3, p4, p1);
 52     //判断p2在线段p3p4的哪一侧
 53     double d2 = direction(p3, p4, p2);
 54     //判断p3在线段p1p2的哪一侧
 55     double d3 = direction(p1, p2, p3);
 56     //判断p4在线段p1p2的哪一侧
 57     double d4 = direction(p1, p2, p4);
 58     //如果相互跨越
 59     if (d1 * d2 < 0 && d3 * d4 < 0)
 60         return true;
 61     //下面四个是边界情况,第一个是点p1在线段P3p4上的时候
 62     else if (d1 == 0 && onSegment(p3, p4, p1))
 63         return true;
 64     else if (d2 == 0 && onSegment(p3, p4, p2))
 65         return true;
 66     else if (d3 == 0 && onSegment(p1, p2, p3))
 67         return true;
 68     else if (d4 == 0 && onSegment(p1, p2, p4))
 69         return true;
 70     return false;
 71 }
 72 //并查集查找
 73 int find(int x)
 74 {
 75     while (x != father[x])
 76         x = father[x];
 77     return x;
 78 }
 79 //合并
 80 void merge(int a, int b)
 81 {
 82     int ta = find(a);
 83     int tb = find(b);
 84     if (ta != tb)
 85     {
 86         father[ta] = tb;
 87         num[tb] += num[ta];
 88     }
 89 }
 90 int main()
 91 {
 92     int t, n;
 93     scanf("%d", &t);
 94     while (t--)
 95     {
 96         int index = 0;        
 97         scanf("%d", &n);
 98         init(n);
 99         char option;
100         for (int i = 0; i < n; i++)
101         {
102             getchar();
103             scanf("%c", &option);
104             if (option == 'P')
105             {
106                 ++index;
107                 scanf("%lf %lf %lf %lf", &a[index].x, &a[index].y, &b[index].x, &b[index].y);    
108                 for (int i = 1; i < index; i++)
109                     if (segment_intersect(a[i], b[i], a[index], b[index]))
110                         merge(i, index);
111             }
112             else
113             {
114                 int k;
115                 scanf("%d", &k);
116                 printf("%d
", num[find(k)]);
117             }
118         }
119         if (t)
120             puts("");
121     }
122     return 0;
123 }

View Code