@Author：Runsen

大四刷題拼offer系列，不拼不行啊

關于：阿里云天池賽在線編程的介紹。

阿里云天池賽在線編程：在線編程限時賽，參與刷題，提升能力，獎品多多，助你晉級拿offer！

本人并沒有參加，而是看看試題，自己不會也當作學習下。

移動的圓

描述：軌跡將指定兩個圓A和B的圓心坐標($x，y$)和半徑$r$，現給你一個點$P$，使圓$A$圓心沿直線運動至點$P$。請問圓$A$在運動過程中是否會與圓B相交？（運動過程包括起點和終點）若會相交返回1，否則返回-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），如圖：

輸入：[0,0,2,5,0,1,0,2] 輸出：-1 樣例解釋：圓A的圓心（0，0），半徑為2，圓B的圓心（5，0），半徑為1，點P（0，2）

難度：中等。一開始就是使用圓相交的判斷條件：$r1?r2<=dis<=r1+r2$。兩個圓相交的充要條件是兩圓圓心距大于兩半徑差的絕對值,小于兩半徑和 ，相切就是加上等于。

考點：點到線段的最短距離，兩個點的距離公式。

關鍵是如何找到運動過程中的最小距離。

最小距離肯定是在同一條直線上，但是也有可能存在不在同一條直線的可能。那么最小距離就是兩個端點值。

但是又有可能是大圓A 里面裝著小圓B （這點必須考慮）

本題的通過率是16.77%。我覺得也很難，浪費了一個早上。考試就給你半個小時一題，可見我是多少的菜比。下面是自己的通過代碼，其實想多下，就很簡單

@Author： Runsen @微信公眾號： 潤森筆記 @博客： https://blog.csdn.net/weixin_44510615 @Date： 2020/8/28 '''class Solution:"""@param position: the position of circle A,B and point P.@return: if two circle intersect return 1, otherwise -1."""def IfIntersect(self, position):x1, y1, r1, x2, y2, r2, xp, yp = position# 向量的表示vector_x1 = x2 - x1vector_y1 = y2 - y1vector_x2 = x2 - xpvector_y2 = y2 - ypvector_x3 = xp - x1vector_y3 = yp - y1# y=ax+b try:a = (y1 - yp) / (x1 - xp)b = y1 - a * x1except ZeroDivisionError:# 存在 0=ax+ba = 1b = (-1) * x1# 直線的距離公式d = abs(a * x2 - y2 + b) / ((a ** 2 + 1) ** (1 / 2))# 如果在圓內沒有接觸 大圓A 里面裝著小圓B （必須考慮） if r1 ** 2 > r2 ** 2 + (x2 - x1) ** 2 + (y2 - y1) ** 2 and r1 ** 2 > r2 ** 2 + (x2 - xp) ** 2 + (y2 - yp) ** 2:return -1# 下面就是常見的情況：向量小于0，說明余弦角大于90，也是就最小距離取不到if (vector_x1 * vector_x3 + vector_y1 * vector_y3) <= 0 or -1 * (vector_x2 * vector_x3 + vector_y2 * vector_y3) <= 0:# 那么最小距離就是兩個端點值，那么就判斷r1+r2 小于就有交集，返回1if (((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5) <= r1 + r2 or (((x2 - xp) ** 2 + (y2 - yp) ** 2) ** 0.5) <= r1 + r2:return 1else:return -1else:# 下面就是角小于90，正常情況if d <= r1 + r2:return 1else:return -1

在查閱的時候，看了標準的做法。代碼我都看不懂，

class Solution:"""@param position: the position of circle A,B and point P.@return: if two circle intersect return 1, otherwise -1."""def IfIntersect(self, position):def getDistance(x, y, x1, y1, x2, y2):dx = x2 - x1dy = y2 - y1# 沒有移動if dx == 0 and dy == 0:dx = x - x1dy = y - y1return float(dx ** 2 + dy ** 2) ** 0.5# what is t ? # r ^ 2 = float(dx ** 2 + dy ** 2)# (x - x1) / r * dx / r # cosine # (y - y1) / r * dy / r # sinet = ((x - x1) * dx + (y - y1) * dy) / float(dx ** 2 + dy ** 2)# if t < 0:dx = x - x1dy = y - y1elif t > 1:dx = x - x2dy = y - y2else:dx = x - (x1 + t * dx)dy = y - (y1 + t * dy)return float(dx ** 2 + dy ** 2) ** 0.5x1, y1, r1, x2, y2, r2, xp, yp = position dis = getDistance( x2, y2, x1, y1, xp, yp)return -1 if not r1 - r2 <= dis <= r1 + r2 else 1

總結

以上是生活随笔為你收集整理的一、为了OFFER系列 | 阿里云天池赛在线编程：移动的圆的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。