Datenstruktur zum Filtern aller paarweisen größeren Punkte?

Question

Was ist eine gute Umsetzung der folgenden?

Die betreffende Datenstruktur darf keinen Punkt enthalten, der paarweise größer als ein anderer ist. z.B. (2,11)> (1,10), (5, 5) nicht-gt (1,5). Und Eingaben erfolgen online, so dass sie nicht vorbestellt/vorbereitet werden können.

Okay, das kann oben mit dem Bild gezeigt werden. So wird jeder Punkt in der angegebenen Reihenfolge eingeführt, wie folgt:

1. (2,2) eingefügt
2. (2,4) eingeführt wird, nicht die> (2,2) und umgekehrt, so bleiben beide
3. (3,3)> (2,2) und so wird nicht eingefügt
4. (1,1); alle anderen> so (1,1) eingefügt während alle anderen entfernt

Ideen?

Answer 1

Einfach verknüpfte Liste mit Punkten, die paarweise weniger als eine andere ist.

Betrachten Sie die Situation der Vergleiche einen neuen Punkt für jeden Punkt in der Liste im aktuellen Schritt. Сheck: unser Punkt weniger als ein Prüfpunkt in der Liste?

Wenn ja, entfernen Sie den Checkpoint von der Liste.

Andernfalls fügen Sie einfach einen neuen Punkt zur Liste hinzu.

Am Ende haben Liste solche Punkte.

Answer 2

Beginnen Sie mit der Anordnung von Punkten (-Inf, Inf) und (Inf, -Inf)

um die Elemente in der Anordnung in Bezug auf unter Regel

for (x,y) and (t,z) 
if x<t (x,t) is before (t,z) 
if x=t and y>z then (x,t) is before (t,z) 

Wenn Sie ein einfügen möchten Element, finde das Element mit der höchsten Ordnung vor dem eingefügten Element und nenne es EBefore. Suchen Sie auch das Element mit der niedrigsten Ordnung, das hinter dem eingefügten Element steht, und nennen Sie es EAfter. Sie können die binäre Suche verwenden, während Sie diese beiden Elemente finden.

Wenn vectoral Produkt von

EInserted x (EAfter - EBefore) > 0 

entfernen Sie die alle elemets zwischen EBefore und ENach ​​und legen EInserted zwischen ihnen. Wenn das Produkt negativ ist, fügen Sie das Element nicht hinzu.