[理工] 演算法考題-只有兩點的smallest circle

作者: iasm (I am Nobody)   2016-05-23 00:17:13
請教各位,我看到一題prune and search應用的smallest circle problem
其題目如下
Give two planar points p1=(a1,b1) and p2=(a2,b2) and a line y=0,
design an algorithm to find the smallest circle that covers
both points such that its center (x*, 0) lies on y=0
由於本題的兩個點並不一定需要在圓周上,故跟原始問題不太像
例如有一點個是(2,5),另一個點是(2,3),由於限制圓心在x軸上
這兩個點又在同一條直線上,因此最小圓的圓心在(2,0),(2,5)在圓周上
(2,3)在"圓內",但如果兩個一個在x軸上,一個在x軸下,那情形又不一樣了
想請問各位,有沒有更為"一般"的演算可以涵蓋所有可能呢?
作者: FRAXIS (喔喔)   2016-05-23 04:53:00
x軸下的情況 應該可以轉成 x 軸上

Links booklink

Contact Us: admin [ a t ] ucptt.com