任何優雅的二叉搜索樹算法來解決這個問題？

我遇到了這個問題，並希望有一個快速的算法來解決這個問題。任何優雅的二叉搜索樹算法來解決這個問題？

給定2D平面中的n個點（它們都沒有x值或y值等於另一個點），找出形成具有正斜率的線的所有點對的數目（例如（0,0 ）和（1,1），正斜率爲45度）

由於n很大（比如60000），所以我需要一個優雅的算法來保持它在1秒內。我知道用O（n^2）很容易做到這一點，但它只不過慢了30秒。是否有可能使用二叉搜索樹來完成nlogn複雜性？

我很欣賞任何想要在這方面給我啓發的人。

來源

2012-04-11 Daniel

好像你應該能夠數學做到這一點..

每套2點有（使用permuations，我相信）要麼是正的還是負的，如果他們是隨機的點，這個手段將會有平均50％的正面和50％的負面。所以這將會是成對的數量/ 2.

來源

2012-04-11 03:01:10 DanRedux

這假設了一個統一的分佈。如果飛機上的點被分組在一條具有負斜率的線周圍，那麼這個數字將會比'countOfPairs/2'少得多，甚至可能爲0. – 2012-04-11 03:28:43

感謝您的即時回覆，但它確實是關於編程，而不是數學。我想知道給定n個點的確切對數，而不是理論上的平均數。任何可以實施的算法建議？ – Daniel 2012-04-11 03:29:22

安德魯，據我瞭解的問題，唯一可能的時機是當他們都完全一致，在這種情況下，如果他們在一個積極線對齊，那麼他們都會創建積極線，所以平均會仍然是countOfPairs/2。丹尼爾，我們知道那些點的位置嗎？沒有具體說明，所以我認爲這是一個假設情況。 – DanRedux 2012-04-11 07:44:07

任何優雅的二叉搜索樹算法來解決這個問題？

回答

相關問題