Plot kolem lesa

Majitel má na pozemku malý lesík, který chce oplotit tak, že plot přidělá přímo na některé ze stromů v lesíku. Plot by měl být co nejkratší, ale všechny stromy by měly být uvnitř oplocení (nebo být součástí plotu). Na které stromy plot přidělá?

V modulu solver.py vytvořte funkci build_fence(), která na základě seznamu souřadnic stromů vrátí indexy těch stromů, na které má být plot přidělán, a to v pořadí, v jakém by se měl plot stavět. Soubor solver.py pak odešlete do odevzdávacího systému.

Zárodek takové funkce může vypadat např. takto:

def build_fence(trees):
    fence = list(range(len(trees)))
    return fence

Tato funkce ale nepracuje správně, vrací indexy všech stromů, a takový plot skoro jistě nesplňuje podmínky uvedené níže. Na vás je upravit funkci tak, aby fungovala podle požadavků.

Funkce build_fence() by měla mít následující vstupy a výstupy:

Doplňující informace:

• Ignorujte tloušťku kmene stromu. Každý strom je ideální bod.
• Na jednom místě nemohou růst dva stromy. Můžete tedy předpokládat, že všechny stromy budou na unikátnách souřadnicích.
• Pokud stromy, na které by měl být plot přidělán, leží přesně na přímce, měly by být ve výstupu uvedeny indexy všech těchto stromů, nejen krajních.
• Funkce build_fence() by měla vrátit plán stavby plotu, tj. indexy stromů v takovém pořadí, v jakém je možné plot okolo lesa postavit. Záleží tedy na pořadí indexů, ale nezáleží na tom, u kterého krajního stromu začneme a kterým směrem kolem lesa se vydáme.
• První strom má index 0, poslední N-1, kde N je počet stromů.
• V plotu se nesmí žádný strom objevit 2x. Spojnice mezi posledním a prvním stromem v plotu bude přidána automaticky.

Na vašem řešení bude provedena série testů na cca 20 různých lesících.

• Vrácený plot musí obsahovat jen platné indexy stromů.
• Plot nesmí sám sebe křížit.

Nebude-li některá z těchto podmínek splněna, hodnocení na zbývajících testovacích lesích nebude provedeno.

Získaný počet bodů se skládá

• z části odvozené od počtu oplocených stromů (čím více, tím lépe),
• z části odvozené od délky plotu (čím méně, tím lépe) a
• z bonusu za správné řešení.