[leetcode/lintcode 题解] 算法面试真题详解：移动的圆

描述
题目将给出两个圆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），如图：

        

          
        
        
        

          

          AI 代码解读
        
      
      

样例2
输入：[0,0,2,5,0,1,0,2]
输出：-1
样例解释：圆A的圆心（0，0），半径为2，圆B的圆心（5，0），半径为1，点P（0，2）

        

          
        
        
        

          

          AI 代码解读
        
      
      

解题思路

其实这个问题做法有很多，在此仅提供一种思路。
这里可以将连线轨迹形成一个矩形，判断矩形和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

        

          
        
        
        

          

          AI 代码解读
        
      
      

更多题解参考：九章官网solution