Extinzand un pic explicatia lui Patrick cu o demonstratie care arata de unde vine solutia respectiva:
In principiu vrem sa determinam in ce conditii o "tragere" intersecteaza o "tinta". Unei tinte oarecare ii corespunde un triplet (x0, y0, y1), iar unei trageri un (x', y', r).
Observam ca punctele de pe traiectoria tragerii sunt de forma (x' + r', y' + r'), 0 <= r' <= r. Pt a avea intersectie, trebuie ca (x' + r', y' + r') sa fie pe dreapta verticala (x0, y0, y1) corespunzatoare tintei, pt un 0 <= r' <= r (exista maxim o intersectie intra o dreapta transversala si una verticala) <=>
exista 0 <= r' <= r, a.i:
1) x0 = x' + r'
2) y0 <= y' + r' <= y1
Observatie 1: singurul r' candidat este r' = x0 - x', care tb sa fie intre 0 si r. Inlocuind in a 2-a conditie avem:
y0 <= y' + r' <= y1 <=> y0 <= y' + x0 - x' <= y1 <=> y0 - x0 <= y' - x' <= y1 - x0
Observatie 2: Avem 2 conditii pt intersectie: una la nivel de x si una la nivel de y dupa cum am vazut mai devreme. Conditia pt y nu depinde deloc de r', si implicit de r. Putem rescrie conditiile de mai devreme ca:
1) x' <= x0 <= x' + r
2) y0 - x0 <= y' - x' <= y1 - x0
De aici ne vine ideea de a ne creea un nou sistem de drepte a.i:
a) "tinta" (x0, y0, y1) -> (x0, y0 - x0, y1 - x0)
b) "tragerea" (x', y', r) -> (x', x' + r, y' - x')
Astfel avem numai drepte orizontale si verticale ; iar o intersectie intre o dreapta verticala si una orizontala respecta conditiile 1) si 2). Aceasta problema este un exemplu clasic de line sweeping prezentat spre ex la
https://www.topcoder.com/community/data-science/data-science-tutorials/line-sweep-algorithms/ sub sectiunea "line segment intersections". Se poate folosi intr-adevar un AIB + Smenul lui mars pt a numara numarul de intersectii intre "portiunea activa" si o dreapta verticala.