finden Sie Kreuzung Linie durch 3 Punkte auf horizontalen Linien

Question

Gegeben eine Gruppe von n Punkten, die auf 3 horizontalen Linien verteilt sind (y = 0, y = 1, y = 2) Denken Sie an Algorithmus zu finden, wenn es Kreuzung mit ist O (n^2)

enter image description here

Answer 1

ich glaube, diesen Algorithmus in O (n^2). Zuerst nehmen wir an:

1. Die x -Koordinaten der Punkte auf der Linie y=2 kann durch eine endliche Anzahl von Bits dargestellt werden.
2. Diese x-Koordinaten sind zunächst in x sortiert. Wenn nicht, dann wird sie zuerst sortiert. O (nlog (n))
3. Die Definition der Kreuzungslinie erfolgt in Bezug auf die Genauigkeit der Darstellung der Punkte mit der endlichen Anzahl von Bits. Jetzt

, bauen eine Hash-Funktion wie folgt:

1. , um einen Mindestabstand zwischen benachbarten Punkten auf der Linie y=2. Da die x -Koordinaten sortiert sind, ist dies O (n). Rufen Sie diese Mindestentfernung d.
2. Die Hash-Funktion ist floor (2 * x/d). Es ist klar, dass dieser Hash jeden Punkt auf y=2 zu einer eindeutigen Bin zuordnen wird. Diese Operation ist ebenfalls O (n).

Dann gehen Sie wie folgt vor: berechnen

1. Für jedes Paar von Punkten auf den Linien y=0 und y=1, seine intersect auf y=2. Das ist O (n^2).
2. Suchen Sie für jeden Schnittpunkt auf y=2 die Hashtabelle, um festzustellen, ob dort ein Punkt aus der Zeile y=2 ist. Wenn dies der Fall ist, sehen Sie, ob es sich um den gleichen Punkt handelt (innerhalb der Genauigkeit der Maschine), und wenn ja, dann gibt es eine Kreuzungslinie. Ansonsten ist es nicht. Dies ist O (n^2), da die Hash-Suche O (1) ist.

Daher ist der Algorithmus O (n^2). Kein Code, nur Ideen.