Próbuję rozwiązać słynny problem z panoramą (patrz gif):

 Wkład

(1,11,5), (2,6,7), (3,13,9), (12,7,16), (14,3,25), (19,18,22), (23 , 13,29), (24,4,28)

Powinny powrócić, punkty znajdujące się za innymi budynkami powinny zniknąć, a współrzędne zmian w osi Y powinny znajdować się w powracającej panoramie:

(1, 11), (3, 13), (9, 0), (12, 7), (16, 3), (19, 18), (22, 3), (23, 13), (29 , 0)

Próbuję to zrobić, stosując podejście algorytmu dziel i zwyciężaj, aby osiągnąć czas działania O (n lg n), ale utknąłem na części scalania.

Za każdym razem, gdy o tym myślę, jestem zdezorientowany. Na przykład sprawdzam, która z nich jest na pierwszym miejscu, np. który ma niższą współrzędną x, dodam, że + jego wysokość do mojej nowej linii horyzontu. Ale kiedy natrafiam na panoramę, która znajduje się za dwiema innymi sylwetkami na tle nieba, jak mogę wykryć tę „kolizję”?

Czy najpierw sprawdzam, czy linie horyzontu mają jakiekolwiek nakładanie się, sprawdzając, czy left.x2 <right.x1? Ale potem myślę, co powinienem najpierw sprawdzić? Nakładanie się pierwszeństwa na osi X i wszystko zmienia się w duży bałagan z kurczakiem.

Może myślę zbyt skomplikowany? Potrzebuję zestawu najwyższych współrzędnych y, na każdym skrzyżowaniu, czy powinienem do tego podejść?