# Zkouška - Mareš 21. 1. 2019

<{ForumPost(poster="NeverNotBluu", timestamp=2019-01-21 12:29:37)}>
1) KMP - popis, analýza, ...  
2) Předseda a tajemník - Máme množinu poslanců a množinu klubů, přičemž každý poslanec může být ve více klubech. Cílem je najít pro každý klub z jeho členů předsedu a tajemníka tak, aby žádný poslanec nezastával více než jednu funkci.  
3) Najděte algoritmus, který hledá průsečíky kružnic (s nápovědou, že půjde o nějakou úpravu průniků přímek)
<{/ForumPost}>

<{ForumPost(poster="NeverNotBluu", timestamp=2019-01-21 23:54:40)}>
**Řešení:**  
2) Vyrobí se bipartitní graf, kde v levé partitě jsou všichni poslanci a v pravé pro každý klub vrchol předsedy a vrchol tajemníka. Hrany se natahají z těchto dvou vrcholů klubu do každého člena toho klubu. Graf se pak klasicky doplní na síť s jednotkovými kapacitami, najde se maximální tok a pozice se pak obsadí podle těch hran, kterými tok teče.  
  
3) Základní myšlenka je taková, že když z kružnice odeberu nejvrchnější a nejspodnější bod, stanou se mi z ní dva oblouky, což už je *skoro* identická úloha. Stačí tedy zametat shora dolů a když najdeme vršek kružnice, vložíme si do průřezu odkazy na K<sub>levá</sub> a K<sub>pravá</sub>. Na spodku kružnice je pak samozřejmě zase zahodíme.  
Tohle už funguje v podstatě identicky s průniky přímek, s tím rozdílem že dva oblouky mohou mít dva společné průsečíky. To ošetřím tak, že a) když najdu průsečíky dvou oblouků, naplánuji si do kalendáře jenom ten nejvrchnější, a b) když narazím na průsečík, musím další průsečíky hledat i v té dvojici, kterou jsem právě prohodil.
<{/ForumPost}>