數據結構和算法（圖形相關）

Question

給出一組N個支桿，它們在某種配置下彼此重疊。每個棒由其兩個端點指定;每個端點都是一個有序的三元組，給出它的x，y和z座標;沒有棍子是垂直的。只有在沒有棍子的情況下，棍子才能被拾起。

a。解釋如何編寫一個需要兩個棍棒a和b的例程，並報告a是高於，低於還是與b無關。 （這與圖論無關。）

• 在x和y軸上的兩個棒的計算範圍。

• 如果a和b的x範圍或a和b的y範圍的交點爲零，則兩個枝不在同一個地方。

• 如果二者都不爲零，則計算兩根棍棒交叉的點（x-y平面中兩條線的交點），並在該點處具有較高z值的棍棒位於頂部。

b。給出一個算法，確定是否有可能拿起所有的棍子，如果是，提供一系列的棍子拾取完成這一點。

我不知道我應該使用什麼算法。

• 對於問題A，請讓我知道，如果它不正確，或者如果它是vauge。

• 對於問題B，請讓我知道哪種算法可能是合適的。

Answer 1

假設有可能拿起所有的棍子。

如果你知道，如果一棒高於另一棒（如你所說，通過比較X-Y，然後Z），那麼你有一個比較的方法來比較它們之間的棒，你可以排序他們。一旦它們被分類，你就從上面的一個開始，然後將其刪除，然後取下並刪除它...

這裏的問題是我們不知道以上是否可能。瞭解上述算法給了你一個提示：當我們不能排序所有的棍子時，我們不能刪除所有的棍子，即如果我們不是有循環，如< b < c < a。

所以你需要找出你的訂購方法是傳遞。傳遞意味着，如果一個< b和b < c然後一個< c，對於所有的棒。

如果您的訂購方法是過渡性的，那麼您可以刪除所有的棒。如果不是，那麼你不能刪除所有的棍子。

要做到這一點，您可以手動使用冒泡排序樣算法你的棍子排序：

對於每個棒：

• 轉到線通過有序棒陣列，直到找到一個棒，這是優越的。
• 記住索引，但仍然通過陣列的其餘部分檢查所有跟隨的棒是否較差
• 如果它們不是，請停止，因爲您的訂單不是傳遞性的。

這有O（n^2）的複雜性。我不知道你能否做得更好。