Zkouška 1.2. 2007 Kučera - postřehy Voronoiuv diagram

Ošklivý sup
Matfyz(ák|ačka) level I
Příspěvky: 49
Registrován: 2. 2. 2006 15:58

Zkouška 1.2. 2007 Kučera - postřehy Voronoiuv diagram

Příspěvek od Ošklivý sup »

Dnešní zkouška od 9, přišel jsem tak akorát a už tam lidi seděli a psali. Vzal sem si otázku a taky začal. Po 14 lidech už další posílal pryč ať přiijdou později (takže ne podle SISu).

Bacha, byla tam i NP problémy. Sem si myslel že tam vůbec nebude ale nějaký chudák to dostal, já se to vůbec neučil :)

Měl jsem Voronoiův diagram, napsal jsem 2 A4 a šel odevzdat asi po 45 minutách jako první.
Měl jsem tam docela dost věcí kolem co měl v materiálech, ale ždáné ty hnusné přesné algoritmy s indexy a tak. Popsal jsem princip slovy, algoritmus pak take slovy. U Místní události a Kruhové události sem napsal co se dělá (vznikne nová parabola, zaniknou kruhové události a vzniknou nové tad). Snad sem napsal vše, ale vůbec sem tam nerozebíral ten jeho šílenej program při místní události....

Pročetl, zeptal se u kruhové události, jaké nové vzniknou když zanikne parabola Pi (tak Pi-2, Pi-1,Pi+1 a druhá Pi-1, Pi+1, Pi+2). To se dá jednoduše domyslet z obrázku když člověk trochu chápe co se děje.

Pak se mě ale zeptal jaké další události mohou při kruhové události zaniknout. Tak to mě dostal, netušil sem co (nechtěl žádné hybridní případy). No při vysvětlování co chce ta otázka zanikla a vznikla nová, o nic moc lepší:

Jak při kruhové události zjistit výšku zametací přímky. To mě trochu uniklo, v materiálech to něměl. Tak říkal že na 1 bych to musel vědět a že za 2.

...jinak: zametací přímka se neposunuje po ose Y spojitě, ale máme jen seznam událostí a u každé události se udržujeme informaci kdy k ní dojde = y-lonová souřadnice zametací přímky v okamžiku kdy k tomu dojde. Pak jen vybereme první událost z fronty a zametací přímku posunem na danou souřadnici. Problém je Kruhová událost (Místní je daná bodem jasně), jak zjistit tu y-lonovou souřadnici, když ji přidáváme jako novou událost do seznamu. No je to nějaká geometrie, na kterou jsem v tu chvíli neměl mozek. Ten bod kde se ty tři paraboly setkají je střed kružnice dané třemi ohnisky těch parabol. Známe tedy kržnici a její střed a tři body na ní. To bylo jasné. No a pak říkal že vzdálenost těch třech bodů od středu je stejná a stejná je i vzdálenost té zemetací přímky která je nahoře tečnou té kružnice. Proč už sem nepochopil (podle mne mohla být kdekoliv vejš :)... tak když někdo budete tušit, doplňte.
Návštěvník

Příspěvek od Návštěvník »

On si na začátku zkoušky hlavně vybírá, kdo je mu sympatickej. Neuměl jsem nic a dostal jsem 2...
Odpovědět

Zpět na „2006“