Kaip efektyviai patikrinti, ar yra atspindžio pora taškų su priešingu x?

Efektyviai patikrinti, ar egzistuoja veidrodinis taškų pora su priešingomis x reikšmėmis, galima naudoti duomenų struktūrą greitam paieškai — pavyzdžiui, rinkinį (set).

Algoritmas:

1. Visus taškus įdėkite į rinkinį, kad būtų galima atlikti O(1) paiešką.
2. Kiekvieno taško (x, y) atveju patikrinkite, ar rinkinyje yra taškas (-x, y).

Jei toks taškas randamas, tai reiškia, kad egzistuoja veidrodinis pora pagal Y ašį.

Python pavyzdys:

points = [(1, 2), (-1, 2), (3, 4), (5, 6)]
point_set = set(points)

for x, y in points:
    if (-x, y) in point_set:
        print(f"Rasta veidrodinė pora: ({x}, {y}) ir ({-x}, {y})")

Šis metodas veikia O(n) laiko, kur n yra taškų skaičius, ir yra efektyvus dideliems duomenų rinkiniams.