目录
题目描述
给出了平面上的n条线段，然后给出m对线段的下标对\((i,j)\)，判断第i条和第j条线段是否相连。
比较坑的地方是：不同线段之间可能间接相连，即通过别的线段依次传递，最终使得两条线段相连。
判断点在直线上的方法
向量a=(x3-x1,y3-y1),向量b=(x2-x1,y2-y1)
\(a \times b > 0\)表示点(x3,y3)在直线(x1,y1)-(x2,y2)的逆时针方向
\(a \times b < 0\)表示点(x3,y3)在直线(x1,y1)-(x2,y2)的顺时针方向
\(a \times b = 0\)表示点(x3,y3)在直线(x1,y1)-(x2,y2)上
struct point{
double x,y;
}
double direct(point p1, point p2, point p3){
return (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
}
bool onLine(point p1, point p2, point p3){
return direct(p1,p2,p3) == 0;
}
判断点在线段上的方法
判断点在线段上有很多种方法：
第一种，通过向量外积先判断点是否在直线上，然后判断点的x和y是否在线段的x和y范围内。
struct point{
double x,y;
}
double direct(point p1, point p2, point p3) {
return (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
}
bool onSegment(point p1, point p2, point p3) {
return (min(p1.x, p2.x) <= p3.x && p3.x <= max(p1.x, p2.x) && min(p1.y, p2.y) <= p3.y
&& p3.y <= max(p1.y, p2.y)) && direct(p1, p2, p3) == 0;
}其中，onSegment函数用来判断第三个点是否在第一，二个点构成的线段上。
第二种，通过向量外积先判断点是否在直线上，然后用向量内积判断点是否在线段上。
struct point{
double x,y;
}
double det(point p1, point p2, point p3) {
return (p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y);
}
double dot(point p1, point p2, point p3, point p4) {
return (p2.x - p1.x) * (p4.x - p3.x) - (p2.y - p1.y) * (p4.y - p3.y);
}
bool onSegment(point p1, point p2, point p3) {
return det(p1, p2, p3) == 0 && dot(p1, p3, p2, p3) <= 0;
}其中，det函数用来计算向量p1p2叉乘p1p3,dot函数用来计算向量p1p2点乘p3p4,onSegment函数用来判断p3是否在p1p2构成的线段上。
