Matematické Fórum

Mám problém s napsáním této ulohy do předmětu PRG. Návod tam sice je, a je pravdou, že postupem jsem si jistý, ale napsat to efektivně a s optimalizacema nejsem schopný. Pokud by byl někdo hodný a pomohl mi to napsat, jsem schopen se mu odvděčit i finančně a samozřejmě, že částka by skutečně odpovídala dané práci.

ZADÁNÍ:

Úkolem je realizovat program, který pro zadané obdélníky určí obvod vzniklého obrazce.

Vstupem programu je seznam obdélníků. Obdélníky mají strany rovnoběžné s osami x a y. Jsou zadány pomocí čtyř celých čísel, která mají význam souřadnic jejich rohů. Čísla jsou zadaná jako x1 y1 x2 y2, kde x1 y1 je souřadnice jednoho rohu a x2 y2 je souřadnice druhého rohu. Pozor - není garantováno, že x1 < x2 ani y1 < y2.

Obdélníky jsou na vstupu zadávané na standardním vstupu postupně, jejich zadávání je ukončeno "koncem std. vstupu", tedy při zadávání z klávesnice stiskem Ctrl-Z (Win) nebo Ctrl-D (UNIX). V programu poznáte ukončení vstupu signalizovaným feof(stdin). Dejte dobrý pozor na správné ošetření vstupu, příznak feof(stdin) testujte vždy až po pokusu o načtení. Pro testování je vhodné data předávat ze souboru přesměrováním na std. vstup Vašeho programu.

Výstupem programu je obvod útvaru, který vznikne sjednocením zadaných obdélníků. Do obvodu nesmí být započteny překryté části stran obdélníků. Pokud složením obdélníků vznikne nepokryté 'díra' uvnitř útvaru, tak se délka obvodu této díry připočte do délky obvodu. Formát výstupu je zřejmý z ukázky níže.

Program musí detekovat chybně zadaná vstupní data. Pokud je chyba detekovaná, musí program vypsat chybové hlášení (formát viz níže) a ukončit se. Za chybu je považováno:

na vstupu byla nečíselná hodnota,
na řádce nebyla zadaná alespoň 4 celá čísla,
délka nebo šířka zadaného obdélníku je nulová,
nebyl zadaný žádný obdélník.
Program je testován v omezeném prostředí, kde je limitovaná doba běhu i velikost dostupné paměti. Pro vyřešení úlohy s bonusem je potřeba trochu optimalizovat algoritmus, aby neprováděl zbytečné operace (zbytečná testování).

Ukázka práce programu:
Zadejte obdelniky:
10 10 20 20
30 30 40 50
Celkovy obvod: 100
Zadejte obdelniky:
10 10 20 20
20 20 40 50
Celkovy obvod: 140
Zadejte obdelniky:
0 0 12 15
10 10 20 20
18 19 30 22
Celkovy obvod: 104
Zadejte obdelniky:
10 10 20 20
0 15 30 17
15 0 17 30
Celkovy obvod: 120
Zadejte obdelniky:
0 0 5 100
20 0 25 100
-10 20 100 25
-10 40 100 45
Celkovy obvod: 800
Zadejte obdelniky:
5 0 15 10
0 10 10 20
10 15 20 25
15 5 25 15
Celkovy obvod: 120
Zadejte obdelniky:
10 10 20 aadds
Nespravny vstup.
Zadejte obdelniky:
10 20 20 20
Nespravny vstup.
Nápověda:
Pamatujte si seznam obdélníků. Obdélníky v seznamu udržujte tak, aby se v něm obsažené obdélníky nepřekrývaly.
U každého obdélníku v seznamu si pamatujte, které hrany jsou pokryté a které ne.
Postupně přidávejte zadávané obdélníky do seznamu. Pokud by se přidávaný obdélník protínal s některým jiným obdélníkem v seznamu, pak přidávaný obdélník, existující obdélník, nebo dokonce oba obdélníky "rozdrobte" na menší obdélníky. Rozbité obdélníky pak přidejte rekurzivně (zde je prostor pro případné optimalizace).
Výsledek získáte průchodem přes seznam obdélníků.