Solutie OyPara (Alexandru Mosoi)

Se face mai intai infasuratoare convexa a punctelor de sus (obtinand
poligonul Ps), si infasuratoarea (poligonul Pj)
convexa a punctelor de jos, reducand astfel problema la a duce o dreapta D 
printre doua poligoane. Daca dreapta ar intersecta poligonul de sus, atunci
unul din varfuri ar fi sub dreapta si deci un segment ar fi sub dreapta.

Daca dreapta D trece printre cele doua poligoane, atunci ea poate fi
translatata astfel incat ea sa atinga un varf A de pe poligonul Ps. Mai mult,
aceasta dreapta poate fi rotita astfel incat sa atinga un varf B in poligonul
Pj.

Pentru fiecare punct J de pe poligonul Pj exista un punct S pe poligonul Ps
astfel poligonul Ps sa fie (in intregime) pe partea + a dreptei JS. Daca 
dreapta JS nu intersecteaza poligonul Pj atunci avem solutie dreapta JS.

Initial consideram punctul J ca fiind cel mai din stanga varf al poligonului
Pj. Cautam, in O(N), punctul S corespunzator. Parcurgand  cu J poligonul Pj in sens
invers-trigonometric, punctul S va parcurge poligonul Ps in sens trigonometric.
O parcurgere completa a punctului J pe poligonul Pj va determina o parcurgere
completa a punctului S pe poligonul Ps. Amortizat, pentru fiecare J putem gasi
S in O(1).

Infasuratoarea convexa se face in O(N*logN).
Verificarea intersectiei dreptei JS cu poligonul Pj se face in O(1).
Calcularea S-ului corespunzator fiecarui J se face in O(1).
Complexitatea totala: O(N*logN) + N * O(1) = O(N*logN).

