2012-04-11 11 views
0

Ich wurde mit diesem Problem konfrontiert, und würde gerne einen schnellen Algorithmus haben, um es auszuarbeiten.irgendein eleganter binärer Suchbaumalgorithmus, um das herauszufinden?

Gegeben n Punkte in der 2D Ebene (keiner von ihnen hat einen x Wert oder y Wert gleich einem anderen), ermitteln Sie die Anzahl aller Punktpaare, die eine Linie mit positiver Steigung bilden (zB (0,0)) und (1,1), mit einer positiven Steigung von 45 Grad)

Da das n groß ist (sagen wir 60000), brauche ich einen eleganten Algorithmus, um es innerhalb 1 Sekunde zu halten. Ich weiß, es ist leicht, es mit O (n^2) zu tun, aber es ist einfach zu langsam, was etwa 30 Sekunden dauert. Ist es möglich, einen binären Suchbaum zu haben, um es mit nlogn Komplexität zu tun?

Ich schätze jeden, der mich dazu aufklären möchte.

Antwort

0

Es scheint, wie Sie mathematisch es in der Lage sein zu tun, sollte ..

Jeder Satz 2 Punkte gibt es (permuations verwenden, glaube ich) wird entweder positiv oder negativ sein und wenn sie zufällig Punkte, bedeutet dies, es wird durchschnittlich 50% positiv und 50% negativ sein. Also wäre es die Anzahl der Paare/2.

+0

Das setzt eine gleichmäßige Verteilung voraus. Wenn die Punkte in der Ebene um eine Linie mit negativer Steigung gruppiert sind, dann ist die Zahl viel kleiner als "countOfPairs/2", vielleicht sogar 0. –

+0

Danke für Ihre sofortige Antwort, aber es geht in der Tat um Programmierung, nicht um Mathematik. Ich möchte die genaue Anzahl der Paare kennen, die irgendwelche n Punkte haben, anstatt eine theoretisch durchschnittliche Zahl zu haben. Jeder Algorithmus Vorschlag, der implementiert werden kann? – Daniel

+0

Andrew, soweit ich die Frage verstehe, ist die einzige Zeit, die möglich ist, wenn sie alle perfekt ausgerichtet sind, in diesem Fall, wenn sie in einer positiven Linie ausgerichtet waren, dann würden alle von ihnen positive Linien erstellen, so würde der Durchschnitt Sei immer noch countOfPairs/2. Daniel, kennen wir die Orte dieser Punkte? Es wurde nicht angegeben, also nahm ich an, dass es sich um eine hypothetische Situation handelte. – DanRedux