Feladat: I.460 Korcsoport: - Nehézségi fok: -
Füzet: 2018/szeptember, 357 - 358. oldal  PDF  |  MathML 
Témakör(ök): Feladat, Programozás, algoritmusok

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 téglalap alakú üveglapra gondolatban egy N×M-es (10N,M10000) négyzethálót helyezünk. Az üveglapot rá merőlegesen P (0PN×M) pontban egy-egy nem polarizált fénysugárral megvilágítjuk úgy, hogy minden fénysugár pontosan egy négyzetre essen. Az üveglapra K (0K1000) darab különböző szélességű és hosszúságú, téglalap alakú polárszűrőt helyezünk el úgy, hogy oldalaik a négyzetháló rácsvonalaira esnek. A polárszűrők érintkezhetnek és átfedhetik egymást, de a lapról nem lóghatnak le. Kétféle polárszűrő van: az egyik a beérkező fényt az üveglap felső oldalával párhuzamosan, a másik arra merőlegesen polarizálja. Az a fénysugár, amely két, egymásra merőlegesen polarizáló polárszűrőre esik, nem jut át az üveglapon.
Készítsünk programot i460 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, P-t és K-t. A következő P sorból a megvilágított négyzetek bal alsó sarkának koordinátáit, utána K sorból a polárszűrők bal alsó, illetve jobb felső sarkának koordinátáit és a polarizációt (p vagy m). A koordináták egész számok, az üveglap bal alsó sarkának koordinátái 1,1. A program írja a standard output egymás utáni három sorába a következő feladatok megoldását:
soroljuk fel a beolvasás sorrendjében azoknak a fényforrásoknak a sorszámát, amelyek fénye nem jut át az üveglapon a polárszűrők miatt;
adjuk meg, hány olyan négyzet van, amelyet nem világítunk meg, de a polárszűrők miatt nem átlátszó;
adjuk meg, melyek azok a polárszűrők, amelyeket eltávolítva a fénysugarak átlépése nem változik (több lehetséges megoldás esetén elég egyet megadni).

Példa:
 
Standard bemenet (a  /  jel újsor karaktert jelöl):Standard kimenet:   15 12 13 153 6 7 8   2 2 / 2 6 / 2 8 / 2 11 / 4 11 / 7 6 / 7 76   10 8 / 13 4 / 13 11 / 14 1 / 14 6 / 14 91 4 8 12   1 2 8 4 p / 1 6 3 10 m / 2 8 6 10 p / 4 11 6 13 m   5 6 10 7 p / 7 5 8 12 m / 9 2 11 11 p / 9 9 14 12 p   10 8 12 10 m / 11 11 12 13 m / 12 3 15 7 p / 13 1 16 2 p     13 4 14 6 m / 13 8 15 10 m / 13 11 15 13 p   
 

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