Útěk ze zajetí

Stradivarius Cain právě prchá ze zajetí šíleného generála. Netuší však, že generál nenechal nic náhodě a ve spánku mu nainstaloval sledovací čip. Teď generála vzbudily poplašné sirény, a rád by věděl, zda se Cain stále nachází uvnitř komplexu, nebo se mu už podařilo uniknout.

Generálovo doupě si lze představit jako (ne nutně konvexní) mnohoúhelník v rovině, Cainův sledovací čip jako bod v rovině. Chceme zjistit, zda se bod nachází uvnitř mnohoúhelníka, nebo mimo něj.

Těžší verze

(za vyřešení můžete dostat až 5 bonusových bodů)

Podobná situace s prchajícími agenty se generálovi nestala poprvé, a tak si najal IT firmu, aby mu vyvinula sledovací algoritmus na míru. Ten dostane na vstupu popis generálova komplexu, může si něco předpočítat a jednou za čas pak přijde dotaz typu "Nachází se bod v komplexu?" Zkuste nějaký takový algoritmus také vymyslet. Důležitý je přitom primárně čas strávený na dotaz, sekundárně čas na předvýpočet.