Zkouška - Martin Mareš - 11.1.2008

[stnicolaus]

Zadání dnešní písemky bylo následující:
1) najděte algoritmus pro výpočet obsah mnohoúhelníku, jehož strany jsou rovnoběžné se souřadnicovými osami a souřadnice jsou celá čísla
2) najděte algoritmus, který zjistí dělitelnost binárně zapsaného čísla 3
3) popište Dinicův algoritmus (včetně důkazu korektnosti a složitostí...)

Jak už tu psali lidé přede mnou, času je víc než dost. Já jsem dnes odcházel po 5 hodinách a nebyl jsem poslední Atmosféra na zkoušce příjemná a dnešní zadání navíc nebylo z nejtěžších.

[Lukas Mach]

Ten polygon z jednicky muze protinat sam sebe nebo ne? Jestli ne, je na to proste vzorecek (pardon, jestli mi neco uchazi, mam pocit, ze takovy veci jsme na minuly rok na ADS II nemeli).

[stnicolaus]

Ten polygon z jednicky muze protinat sam sebe nebo ne? Jestli ne, je na to proste vzorecek (pardon, jestli mi neco uchazi, mam pocit, ze takovy veci jsme na minuly rok na ADS II nemeli).

Nemůže se protínat. Řešení je jednoduché: projdou se postupně všechny body a k obsahu se pořád přičítá y1*(x2-x1).