描述
题目将给出两个圆A和B的圆心坐标(x,y)和半径r,现给你一个点P,使圆A圆心沿直线运动至点P。
请问圆A在运动过程中是否会与圆B相交?(运动过程包括起点和终点)
若会相交返回1,否则返回-1。
两个圆的半径均不超过10000。
横纵坐标值的绝对值均不超过10000。
输入数组的意义为[XA,YA,RA,XB,YB,RB,XP,YP]。
在线评测地址:领扣题库官网
样例1
输入:[0,0,2.5,3,2,0.5,0,2]
输出:1
样例解释:圆A的圆心(0,0),半径为2.5,圆B的圆心(3,2),半径为0.5,点P(0,2),如图:
样例2
输入:[0,0,2,5,0,1,0,2]
输出:-1
样例解释:圆A的圆心(0,0),半径为2,圆B的圆心(5,0),半径为1,点P(0,2)
解题思路
其实这个问题做法有很多,在此仅提供一种思路。
这里可以将连线轨迹形成一个矩形,判断矩形和B是否相交。然后在起点和终点特殊判断。
class Solution:
"""
@param position: the position of circle A,B and point P.
@return: if two circle intersect return 1, otherwise -1.
"""
#叉积AB×AC
def xmult(self, B, C, A):
return (B[0] - A[0])*(C[1] - A[1]) - (C[0] - A[0])*(B[1] - A[1])
#两点间距离
def distance(self, A, B):
return math.sqrt((A[0] - B[0])*(A[0] - B[0]) + (A[1] - B[1])*(A[1] - B[1]))
#点A到直线BC距离
def dis_ptoline(self, A, B, C):
return abs(self.xmult(A,B,C))/self.distance(B,C)
def IfIntersect(self, position):
A = [position[0], position[1]]
ra = position[2]
B = [position[3], position[4]]
rb = position[5]
P = [position[6], position[7]]
#过点B作直线AP的垂线,M为该垂线上一点(A和P不重合时M点不与B重合)
M = [B[0] - (P[1] - A[1]), B[1] + (P[0] - A[0])]
dmin = 0.0
dmax = 0.0
#若圆A移动过程中会经过B点到直线AP垂线的交点
if self.xmult(A, B, M) * self.xmult(B, P, M) > 0 :
dmin = self.dis_ptoline(B, A, P)
else :
dmin = min(self.distance(A, B), self.distance(P, B))
dmax = max(self.distance(A, B), self.distance(P, B))
if dmin > ra + rb or dmax < abs(ra - rb):
return -1
return 1
更多题解参考:九章官网solution