感谢大佬的代码和讲解线段相交
题目
题目描述
平面直角坐标系中有一条线段 AB 和一条线段 CD ,求线段 CD 和线段 AB 的相交判断。
输入描述
第一行输入一个 T ,代表测试数据量
每组测试数据输入有两行，每行两个实数坐标 (x,y) 分别代表 A,B,C,D 四个点。
输出描述
若 AB 与 CD 规范相交， 输出 2。
若 AB 与 CD 不规范相交， 输出 1。
若 AB 与 CD 不相交， 输出 0。
输入输出样例
示例 1
输入
1. 3 2. 6 2 3 4 3. 4 5 2 2 4. 7 7 10 1 5. 7 7 3 9 6. 1 6 3 5 7. 2 5 1 4
输出
1. 2 2. 1 3. 0
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
思路
我i们设定两个判定条件：
1.判定两条线段所在的最小矩形是否有重叠的部分：
这条判断标准的原理很简单，如果两条线段所在的最小矩形都没有重叠部分，那么两条线段就不可能相交，我们只需要比较线段的两个端点的x,y值就可以判定
2.通过叉乘判断A，B，C，D四个点的相对位置，这里是叉乘的解释定义
我们发现，当我们在判断c,d是否在ab两端时，如果ca和ab的叉乘与da和ab的叉乘符号相反，就说明c,d在ab的两端。我们判断ab是否在cd两端时也是用同样的思路。只有ab和cd都在对方的两端时，才说明两个线段相交。
规范相交：线段的端点不在另一条线段上
不规范相交：线段的端点在另一条线段上
本题要求我们求规范和不规范相交，我们只需要稍微改一下判定条件
代码1
1. class point(): #定义类 2. def __init__(self,x,y): 3. self.x=x 4. self.y=y 5. 6. def cross(p1,p2,p3): 7. #跨立实验,先求向量p1p2和向量p1p3，再求他们的叉乘 8. x1=p2.x-p1.x 9. y1=p2.y-p1.y 10. x2=p3.x-p1.x 11. y2=p3.y-p1.y 12. return x1*y2-x2*y1 13. 14. def IsIntersec(p1,p2,p3,p4): #判断两线段是否相交 15. 16. #快速排斥，以l1、l2为对角线的矩形必相交，否则两线段不相交 17. if(max(p1.x,p2.x)>=min(p3.x,p4.x) #矩形1最右端大于矩形2最左端 18. and max(p3.x,p4.x)>=min(p1.x,p2.x) #矩形2最右端大于矩形最左端 19. and max(p1.y,p2.y)>=min(p3.y,p4.y) #矩形1最高端大于矩形最低端 20. and max(p3.y,p4.y)>=min(p1.y,p2.y)): #矩形2最高端大于矩形最低端 21. 22. #若通过快速排斥则进行跨立实验 23. if(cross(p1,p2,p3)*cross(p1,p2,p4)<0 24. and cross(p3,p4,p1)*cross(p3,p4,p2)<0): 25. D=2 26. elif (cross(p1,p2,p3)*cross(p1,p2,p4)==0 27. and cross(p3,p4,p1)*cross(p3,p4,p2)==0): 28. D=1 29. else: 30. D=0 31. return D 32. 33. t=int(input()) 34. for i in range(t): 35. p1,p2,p3,p4=point(0,0),point(0,0),point(0,0),point(0,0) 36. x=list(map(float,input().split())) 37. y=list(map(float,input().split())) 38. p1.x,p1.y=x[0],x[1] 39. p2.x,p2.y=x[2],x[3] 40. p3.x,p3.y=y[0],y[1] 41. p4.x,p4.y=y[2],y[3] 42. print(IsIntersec(p1,p2,p3,p4))
代码2
通过元组输入数据，有些难懂，思路和代码1一样，仅作参考
1. 2. def Cross(a,b,c): 3. return (c[1]-a[1])*(b[0]-a[0])-(c[0]-a[0])*(b[1]-a[1]) 4. 5. 6. def intersection(a,b,c,d): 7. if max(a[0],b[0])<min(c[0],d[0]) or max(a[1],b[1])<min(c[1],d[1])\ 8. or min(a[0],b[0])>max(c[0],d[0]) or min(a[1],b[1])>max(c[1],d[1]): 9. print(0) 10. return 11. #print(Cross(a,b,c)*Cross(a,b,d)) 12. #print(Cross(c,d,a)*Cross(c,d,b)) 13. if Cross(a,b,c)*Cross(a,b,d)>0 or Cross(c,d,a)*Cross(c,d,b)>0: 14. print(0) 15. return 16. if Cross(a,b,c)*Cross(a,b,d)==0: 17. print(1) 18. return 19. print(2) 20. return 21. 22. t=int(input()) 23. for i in range(t): 24. x=list(map(float,input().split())) 25. y=list(map(float,input().split())) 26. a,b=list((x[0],x[1])),list((x[2],x[3])) 27. c,d=list((y[0],y[1])),list((y[2],y[3])) 28. intersection(a,b,c,d)
