Kezdőlap


Feladat:	I.400	Korcsoport: -	Nehézségi fok: -
Füzet:	2016/április, 228 - 229. oldal		PDF \| MathML

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Egy $N \times M$ ( $10 \leq N, M \leq 10 000$ ) téglalap alakú területen $K$ ( $0 \leq K \leq 1 000$ ) darab különböző szélességű és hosszúságú téglalap elszórtan helyezkedik el. A téglalapok oldalai párhuzamosak a terület oldalaival, érintkezhetnek és átfedhetik egymást, de a területről nem nyúlhatnak ki.
Készítsünk programot i400 néven, amely a következő problémákat oldja meg.
A program olvassa be a standard input első sorából $N$ -et, $M$ -et és $K$ -t, majd a következő $K$ sorból a téglalapok bal felső, illetve jobb alsó sarkainak $X$ és $Y$ koordinátáit (egész számok).
A program írja a standard outputra a kérdésekre adott válaszokat soronként:

‐	soroljuk fel a beolvasás sorrendjében azoknak a téglalapoknak a sorszámát, amelyek a terület határához hozzáérnek;

‐	adjuk meg, hogy melyik az a téglalap, amelyik a legtöbb más téglalap valamelyik csúcsát tartalmazza; a számításnál az érintkezést ne vegyük figyelembe, több azonos téglalap esetén elegendő egyet megadni;

‐	adjuk meg, hogy hány olyan téglalap van, amely a többitől független, azaz nem ér egyetlen másik téglalaphoz sem, nem metszi, nem tartalmaz egy másikat sem, illetve őt sem tartalmazzák.

Példa (amelyben az újsor karakterek egy részét a tömörség kedvéért / jellel helyettesítettük):

\begin{matrix} Standard bemenet: & Standard kimenet: \\ 16 13 15 & 1 2 4 10 12 15 \\ 1 2 8 4 / 1 6 3 10 / 4 8 6 10 / 4 11 6 13 / & 8 \\ 5 6 10 7 / 7 5 8 12 / 9 2 11 5 / 9 9 14 12 / & 6 \\ 10 8 12 10 / 11 11 12 13 / 12 3 15 7 / 13 1 16 2 / \\ 13 4 14 6 / 13 8 15 10 / 13 11 15 13 \end{matrix}

Beküldendő egy tömörített i400.zip állományban a program forráskódja és rövid dokumentációja, amely tartalmazza a megoldás rövid leírását, és megadja, hogy a forrásállomány melyik fejlesztő környezetben fordítható.