先说一下题目大意：给定一些线段，这些线段顺序编号，这时候如果两条线段相交，则把他们加入到一个集合中，问给定一个线段序号，求在此集合中有多少条线段。
这个题的难度在于怎么判断线段相交，判断玩相交之后就是怎么找个他们之间的联系，这时候就要用到并查集了。
步骤：
1.判断两条线段相交
2. 用并查集实现查找线段个数和添加到集合中
关于这个判断线段相交的问题。我搞了一晚上加上一下午，刚开始自己想了一种数学上的相交，就是先求出两条线段所在的线性方程，然后求出他们的交点，最后在判断这个交点在不在这两个线段之间。这种方式刚开始一想挺简单的，但是在判断在不在两个线段之间就显得比较麻烦了，而且刚开始还漏了一种情况，就是在他们斜率不存在时怎么求出方程来，当时没有考虑这一点直接wa了，后来又加上了这种情况才AC了。
还有一种方法就是利用向量来判定线段是否相交，这个我是看的算法导论上的，答题思路就是判断其中一条线段是否横跨另一条线段，如果这两条线段都互相横跨另一条，那么一定相交，当然还有边界条件，就是这个交点是边界在线段的终点的情况，那具体怎么判断一条线段是否横跨另外一条线段呢，这时候用到向量了，两个向量p1，p2,如果他们的叉乘积大于0，就说明p1位于p2的逆时针的方向，小于0顺时针，等于0共线。所以这一步很关键。当解决了这个问题之后，那么就好办了，如果一条线段的一个点在顺时针侧，一个点在逆时针侧，那么这条线段横跨另一条直线，注意是直线，还不是线段，如果同时另外一条线段也横跨这一条，那么这时就是两个线段相互横跨了，就是相交了。还有一个关键点就是在边界情况下(就是一条线段的一个端点在另一条线段上的时候)怎么办，这时候用到上面写好的函数来判断，如果返回值是0，那么就是临界条件，这时候判断其中一个端点和另外一条线段的关系就行了，如果都不满足上面的这些情况，肯定是不相交了。
还有一点需要注意，在利用并查集实现的时候，要用两个，一个是普通的并查集来存放它们之间的关系，还有一个是存放它们当前集合的数目。具体代码如下；
代码一(第一种判断线段相交的方式)（后来证明可能有些数据过不了，不建议用这个）
#include<iostream>
#include <cstdio>
#include <cstring>
#define EPS 1e-8
using namespace std;
const int N = ;
struct point{
double x, y;
};
struct segmnt{
point ori, des;
};
int father[N], num[N];//father用来保存相交的线段的集合，num表示当前线段所在集合有多少条线段
segmnt seg[N];
//初始化
void init(int n)
{ for (int i = ; i <= n; i++)
{
father[i] = i;
num[i] = ;
}
}
//判断线段是否相交
bool is_Cross(segmnt s1, segmnt s2)
{
point p1, p2, p3, p4;
p1 = s1.ori; p2 = s1.des;
p3 = s2.ori; p4 = s2.des;
//当第一条线段斜率不存在，第二条斜率存在时
if (p1.x == p2.x && p3.x != p4.x)
{
double k = (p4.y - p3.y) / (p4.x - p3.x);
double y = k * (p1.x - p3.x) + p3.y;
return ((y - p1.y >= EPS && y - p2.y <= EPS) || (y - p1.y <= EPS && y - p2.y >= EPS));
}
//当第一条线段斜率存在，第二条斜率不存在时
else if (p3.x == p4.x && p1.x != p2.x)
{
double k = (p2.y - p1.y) / (p2.x - p1.x);
double y = k * (p3.x - p1.x) + p1.y;
return ((y - p3.y >= EPS && y - p4.y <= EPS) || (y - p3.y <= EPS && y - p4.y >= EPS));
}
//当第一条第二条斜率都不存在时
else if (p1.x == p2.x && p3.x == p4.x)
{
return p1.x == p3.x;
}
//当他们斜率都存在时，先求出方程，然后求出他们的交点，判断交点是否在两条线段上
double k1 = (s1.des.y - s1.ori.y) / (s1.des.x - s1.ori.x);
double k2 = (s2.des.y - s2.ori.y) / (s2.des.x - s2.ori.x);
double x0 = (k1 * s1.ori.x - k2 * s2.ori.x + s2.ori.y - s1.ori.y) / (k1 - k2);
double y0 = k1 * (x0 - s1.ori.x) + s1.ori.y;
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)))
return true;
return false;
}
//并查集查找
int find(int x)
{
while (x != father[x])
x = father[x];
return x;
}
//合并
void merge(int a, int b)
{
int ta = find(a);
int tb = find(b);
if (ta != tb)
{
father[ta] = tb;
num[tb] += num[ta];
}
}
int main()
{
int t, n;
scanf("%d", &t);
while (t--)
{
int index = ;
scanf("%d", &n);
init(n);
char option;
for (int i = ; i < n; i++)
{
getchar();
scanf("%c", &option);
if (option == 'P')
{
++index;
scanf("%lf %lf %lf %lf", &seg[index].ori.x, &seg[index].ori.y, &seg[index].des.x, &seg[index].des.y);
for (int i = ; i < index; i++)
if (is_Cross(seg[i], seg[index]))
merge(i, index);
}
else
{
int k;
scanf("%d", &k);
printf("%d\n", num[find(k)]);
}
}
if (t)
puts("");
}
return ;
}
代码二(第二种判断线段相交方式)
#include<iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = ;
struct point{
double x, y;
};
int father[N], num[N];//father用来保存相交的线段的集合，num表示当前线段所在集合有多少条线段
point a[N], b[N];//a代表一个线段的起点，b代表终点
//初始化
void init(int n)
{ for (int i = ; i <= n; i++)
{
father[i] = i;
num[i] = ;
}
}
double Min(double a, double b)
{
return a < b ? a : b;
}
double Max(double a, double b)
{
return a > b ? a : b;
}
//用来判断点c在线段ab的哪一侧，如果返回正值就是逆时针那侧，如果是负值就是顺时针那侧
double direction(point a, point b, point c)
{
point t1, t2;
t1.x = c.x - a.x; t1.y = c.y - a.y;
t2.x = b.x - a.x; t2.y = b.y - a.y;
return (t1.x * t2.y - t1.y * t2.x);
}
//前提条件已知ac和ab共线了，判断点c是否在线段ab上，如果是就返回true；
bool onSegment(point a, point b, point c)
{
double minx, miny, maxx, maxy;
minx = Min(a.x, b.x);
maxx = Max(a.x, b.x);
miny = Min(a.y, b.y);
maxy = Max(a.y, b.y);
return (c.x >= minx && c.x <= maxx && c.y >= miny && c.y <= maxy);
}
//判断线段是否相交，线段一是p1p2, 线段二是p3p4,如果相交返回true；
bool segment_intersect(point p1, point p2, point p3, point p4)
{
//判断p1在线段p3p4的哪一侧
double d1 = direction(p3, p4, p1);
//判断p2在线段p3p4的哪一侧
double d2 = direction(p3, p4, p2);
//判断p3在线段p1p2的哪一侧
double d3 = direction(p1, p2, p3);
//判断p4在线段p1p2的哪一侧
double d4 = direction(p1, p2, p4);
//如果相互跨越
if (d1 * d2 < && d3 * d4 < )
return true;
//下面四个是边界情况,第一个是点p1在线段P3p4上的时候
else if (d1 == && onSegment(p3, p4, p1))
return true;
else if (d2 == && onSegment(p3, p4, p2))
return true;
else if (d3 == && onSegment(p1, p2, p3))
return true;
else if (d4 == && onSegment(p1, p2, p4))
return true;
return false;
}
//并查集查找
int find(int x)
{
while (x != father[x])
x = father[x];
return x;
}
//合并
void merge(int a, int b)
{
int ta = find(a);
int tb = find(b);
if (ta != tb)
{
father[ta] = tb;
num[tb] += num[ta];
}
}
int main()
{
int t, n;
scanf("%d", &t);
while (t--)
{
int index = ;
scanf("%d", &n);
init(n);
char option;
for (int i = ; i < n; i++)
{
getchar();
scanf("%c", &option);
if (option == 'P')
{
++index;
scanf("%lf %lf %lf %lf", &a[index].x, &a[index].y, &b[index].x, &b[index].y);
for (int i = ; i < index; i++)
if (segment_intersect(a[i], b[i], a[index], b[index]))
merge(i, index);
}
else
{
int k;
scanf("%d", &k);
printf("%d\n", num[find(k)]);
}
}
if (t)
puts("");
}
return ;
}