se rozhodneme, zda se vydat doleva nebo doprava.
Prùøez obsahuje v¾dy nejvý¹e~$n$ úseèek, tak¾e operace se stromem budou
-trvat $\O(\log n)$. V~kalendaøi se nachází nejvý¹e~$n$ zaèátkù a koncù
+trvat $\O(\log n)$. V~kalendáøi se nachází nejvý¹e~$n$ zaèátkù a koncù
a nejvý¹e~$n$ prùseèíkových událostí (ty plánujeme pro dvojice úseèek
sousedících v~prùøezu, a~tìch je v¾dy nejvý¹e~$n$). Operace s~kalendáøem
proto trvají také $\O(\log n)$.
ve~Voroného diagramu a takové neexistují, nebo» ka¾dá stìna je ohranièena rovnými
èarami.
-Voroneho diagram pro $n$~zadaných bodù je tedy velký $\O(n)$. Dodejme, ¾e ho lze
-zkonstruovat zkonstruovat v èase $\O(n \log n)$, napøíklad pomocí zametání roviny nebo metodou
+Voroného diagram pro $n$~zadaných bodù je tedy velký $\O(n)$. Dodejme, ¾e ho lze
+zkonstruovat v èase $\O(n \log n)$, napøíklad pomocí zametání roviny nebo metodou
Rozdìl a panuj. Tím se v¹ak zabývat nebudeme,\foot{Pro zvídavé, kteøí nemají zkou¹ku druhý den ráno: Detaily naleznete v~zápiscích z~ADS z~roku 2007/2008.}
místo toho si uká¾eme, jak v ji¾ spoèteném Voroného diagramu rychle hledat nejbli¾¹í body.
odpovídá na jejich dotazy. Medvìdi tak nemusí v mapách nic hledat, staèí se pøipojit na server a poèkat na odpovìï.} Nejprve pøedzpracujeme zadané
mnohoúhelníky a vytvoøíme strukturu, která nám umo¾ní rychlé dotazy na jednotlivé body.
-Uka¾me si pro zaèátek øe¹ení bez pøedzpracování. Rovinu budeme zametat pøímkou shora dolù. Podobnì jako pøi hledání prùseèíkù úseèek, udr¾ujeme si prùøez
+Uka¾me si pro zaèátek øe¹ení bez pøedzpracování. Rovinu budeme zametat shora dolù vodorovnou pøímkou. Podobnì jako pøi hledání prùseèíkù úseèek, udr¾ujeme si prùøez
pøímkou. V¹imnìte si, ¾e tento prùøez se mìní jenom ve vrcholech mnohoúhelníkù. Ve chvíli, kdy narazíme na hledaný bod, podíváme se, do kterého
intervalu v prùøezu patøí. To nám dá mnohoúhelník, který nahlásíme. Prùøez budeme uchovávat ve vyhledávacím stromì. Takové øe¹ení má slo¾itost $\O(n
\log n)$ na dotaz, co¾ je hroznì pomalé.
projects / ads2.git / blobdiff