[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),如图:
样例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

上一篇:[leetcode/lintcode 题解] 阿里巴巴面试题:金字塔


下一篇:[leetcode/lintcode 题解] 阿里算法面试真题:丑数 II · Ugly Number II