[理工] 算法考题-只有两点的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