Az I. 400. feladat (2016. április)

I. 400. Egy \(\displaystyle N\times M\) (\(\displaystyle 10\le N,M\le 10\,000\)) téglalap alakú területen \(\displaystyle K\) (\(\displaystyle 0\le K\le 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 \(\displaystyle N\)-et, \(\displaystyle M\)-et és \(\displaystyle K\)-t, majd a következő \(\displaystyle K\) sorból a téglalapok bal felső, illetve jobb alsó sarkainak \(\displaystyle X\) és \(\displaystyle 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):

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ó.

(10 pont)

A beküldési határidő 2016. május 10-én LEJÁRT.

Mintamegoldás és értelmezés:

Szakali Benedek 10. osztályos tanuló Kecskemét, Kecskeméti Bányai Júlia Gimnázium megoldása: main.cpp

A terület határához érőket úgy szűrtem ki, hogy megvizsgáltam, van-e olyan koordinátájuk, ami a minimum vagy maximum értéket veszi fel.

A második feladatnál egy téglalap akkor tartalmaz egy csúcsot, ha a csúcs mindkét koordinátája a téglalap határain belül van.

A harmadik feladatnál azokat az eseteket vizsgáltam meg, amikor a másik téglalap nem lép kapcsolatba az éppen vizsgálttal. Ez akkor van így, ha a másik téglalap legkisebb x vagy y koordinátája is nagyobb, mint az éppen vizsgált téglalap legnagyobbja, illetve a másik téglalap legnagyobb x vagy y koordinátája is kisebb, mint az éppen vizsgált legkisebbje. Ha a vizsgálat hamis eredményt ad vissza, az éppen aktuális téglalap már nem lehet független.

Statisztika:

7 dolgozat érkezett.
10 pontot kapott:	Hamrik Szabin, Kovács 246 Benedek, Nagy Ábel, Olexó Gergely, Szakali Benedek.
6 pontot kapott:	1 versenyző.
1 pontot kapott:	1 versenyző.

A KöMaL 2016. áprilisi informatika feladatai