快速算法得到的多點共線最外點

Question

我有多個未分類的2D點P0，P1，P2，...，光合速率所有是共線的。我想盡可能快地獲得距離最遠的* P_0 *和* P_n *。

P0   P1  P2 P3     Pn 
|-----------|--------|----|--------------------| 

我不知道如何做到這一點，但用蠻力算法計算所有距離和排序點。任何想法？

Answer 1

如果點是共線的，那麼可以通過直接比較它們的座標來比較它們。您無需計算距離原點或點之間的距離。而且您不需要對整個列表進行排序以獲取最小值和最大值。

僞代碼：

min = p0 
max = p0 
for each point p 
    if p.X < min.X || p.Y < min.Y then min = p 
    if p.X > max.X || p.Y > max.Y then max = p 

你可以用算法有點不甘示弱：有沒有必要檢查Y除非X值都是相同的。