Soutěž: Machr na OOP - Tvorba silniční sítě

Vítám Vás u dalšího machra na OOP a algoritmy. Vašim úkolem bude navrhnout silniční síť pro část krajiny podle zadaných kritérií. Algoritmus a OOP budou hodnoceny nezávisle na sobě. Placky budou rozdány pro OOP i pro algoritmus.

Povolené jazyky jsou kromě C# také Java, C++ a PHP. Další jazyky po konzultaci se mnou. Pokud povolím další jazyk, uvedu to v komentářích, proto prosím čtěte i komentáře.

Zadání

Program si bude muset přečíst data ze souboru input.txt a výstup uložit do souboru output.txt. Program se bude skládat z několika částí, které lze do určité míry řešit samostatně. Celkový počet bodů bude rozdělen mezi pod úkoly. Souřadnice jsou udávány v pravoúhlém souřadnicovém systému. Ukázkový „input.txt“ :

MESTA
0: 12.60; 14.80
1: 18.40; 20.40
2: 14.60; 18.70

SILNICE
0: 14; 3.00
1: 25; 2.00
2: 48; 0.50

FINANCE
565

PODMINKY
1; 2; 4.00
0; 2; 21.60

KRAJINA
2.50; 5.00; 6.00; 10.00; 11.00
0.40; 2.00; 2.00; 2.20; 3.10

1. - Program v souboru dostane tabulku měst a dostupných silnic. Město je určeno svou pozicí v pravoúhlé soustavě souřadnic. Silnice je určena svoji cenou a časem, který odpovídá jednotkové délce silnice (řekněme 1 kilometr). Města budou vždy minimálně dvě, cesta vždy minimálně jedna.

• Město s indexem 0 je na pozicích X[12.6, 14.8]
• Město s indexem 1 je na pozici Y[18.4, 20.4]
• Silnice s indexem 0 stojí 14 korun na jednotku délky a cesta bude trvat 3 minuty
• Pokud postavím silnice typu 0 mezi městy s indexy 0 a 1, bude cena dálnice |XY|*14 = 8 * 14 = 112 korun a cesta bude trvat |XY| * 3.0 = 24 minut. Poznámka: |XY| je vzdálenost mezi městy 0 a 1.

Vašim úkolem bude spojit všechny města tak, aby se dalo z každého města dostat do libovolného jiného města (každé město musí být připojeno k silniční síti). Silnice můžou být pouze přímé a postaveny mezi dvěma městy.

2. - V souboru budou dále uvedeny finance a podmínky, které silniční síť musí splňovat. Finance bude číslo, které nesmíte překročit. Podmínky jsou definované jako index počátečního města, index cílového města a čas, který nesmí cesta překročit.

• Celkem mám na výstavbu 565 korun
• Z města o indexu 1 se musím dostat do města o indexu 2 za 4 minuty
• Z města o indexu 0 se musím dostat do města o indexu 2 za 21.6 minuty

Úkolem bude navrhnout silniční síť tak, aby podmínky splnila a nepřekročila dostupné finance. Počet dostupných financí bude v souboru vždy, podmínky být uvedeny nemusí (poté by byl uveden pouze nápis PODMINKY bez záznamů). Počet řešení, které podmínky i maximálně finance splňují, může být několik. Stačí vypočítat pouze jedno.

3. - V souboru bude uveden seznam krajin, které se v regionu vyskytují. Rychlost provozu na silnici závisí na vzhledu krajiny. Krajina může rychlost provozu zpomalit nebo zrychlit. První číslo je konstanta, která bude násobit čas pro danou silnic v této krajině. Další čtyři parametry určují obdélník (krajiny mají pouze obdélníkový tvar) – počáteční bod (x,y) a rozměry obdélníku (šířka a výška).

• První krajina násobí potřebný čas konstantou 2.5 – bude-li silnice o indexu 0 probíhat touto krajinou, je potřeba počítat 2.5*3.0=7.5 minuty na jednotku délky.
• První krajina má levý horní roh v souřadnicích 5,6 a dolní pravý roh v souřadnicích 5+10 = 15, 6+11 = 17.

Vašim úkolem bude navrhnout silniční síť tak, aby byly splněny předcházející podmínky a zároveň byly do výpočtu zahrnuty krajiny.

Čísla, která jsou zapsány v ukázkovém vstupním souboru s desetinou čárkou, budou mít vždy dvě desetinná čísla. Počet různých měst, cest, podmínek a krajin může být maximálně 1000.
Testovací soubory budou připraveny tak, že bude vždy možné spojit všechny města, dodržet podmínky a vlézt se do rozpočtu – bude vždy existovat alespoň jedno řešení. Pro úspěšné splnění testu stačí najít pouze jedno řešení.

Připravil jsem testovací soubory, na kterých můžete aplikaci vyzkoušet. Můžete je najít zde.

Výstupní formát

Do výstupního souboru bude program vypisovat pouze silnice, které budou spojovat jednotlivé města. Bude se jednat o sérii celých čísel, oddělené středníkem. Bude uvedeno město, ze kterého silnice vychází, dále město, do kterého silnice vede a typ silnice, kterou program použil. Pro ukázkový příklad a první úkol (spojení všech měst), může soubor vypadat následovně:

0;1;1
1;2;2

Město o indexu 0 je spojeno s městem o indexu 1 silnicí typu 1. Město o indexu 1 je spojeno s městem o indexu 2 silnicí typu 2.