Dividere in modo uniforme una serie di punti sul piano e ordinarlo

Question

Input: un set di punti P (x, y). Ci sono due versioni di esso: PX, ordinate per X e Py, ordinate per Y.

Output: le due metà delle metà di PX, ordinate per Y.

Il trucco qui è che deve funzionare in tempo lineare, altrimenti è piuttosto inutile. Quello che ho escogitato finora è trovare il punto medio di PX, chiamiamolo PX [Mid] e quindi iterando su PY, controllando se la coordinata X di ogni punto è più grande di PX [Mid] e quindi assegnandolo alla metà appropriata .

Esempio:

Px = [(1,7),(2,3),(3,1),(4,-2)]
Py = [(4,-2),(3,1),(2,3),(1,7)]
Px[midpoint] = (2,3)
Ly = [(2,3),(1,7)]
Ry = [(4,-2),(3,1)]

Funziona abbastanza bene, se spieghi punti con coordinate X uguali e confronta invece tali punti di Y (e viceversa), il che li ordina in un modo che evita potenziali sorprese. Dove fallisce è il seguente caso:

Px = [(1,7),(2,-3),(2,-3),(4,-2)]
Py = [(2,-3),(2,-3),(4,-2),(1,7)]
midpoint = 2
P[midpoint] = (2,-3)
Ly = [(2,-3),(2,-3),(1,7)]
Ry = [(4,-2)]

Non riesco a pensare a un modo per escludere punti non distinti dalla metà sinistra, quando sono uguali al punto medio. Ancora una volta, tieni presente che questo deve funzionare in tempo lineare, quindi non posso semplicemente dividere PX in due metà e cercare punti che potrebbero appartenere ad esso per il caso strano.