Egy ház tervrajzát egységnyi négyzetrácsos lapon készítik. Minden szobának téglalap alakúnak kell lenni. Eddig N szobát rajzoltak fel a tervrajzon. Minden szobát a bal felső és jobb alsó sarkával adnak meg. A négyzetrács egy mezőjét x-és y-koordinátájával adják meg, a bal felső mező koordinátái (0,0). Az x-koordináták a vízszintesen, az y-koordináták függőlegesen nőnek. A tervező ki akarja számítani, hogy hány új téglalap alakú szobát lehet még betenni a tervbe, ha bármely két új szoba bármely két oldalának nem lehet közös része, továbbá mind a négy oldala szomszédos vagy meglevő szobával, vagy a ház oldalával. Eddig betervezett szobák olyanok, hogy minden szabadon maradt terület téglalap alakú.
Feladat
Készíts programot, amely az épület és a tervben meglévő szobák ismeretében megadja, hogy hány téglalap alakú új szobát lehet még betenni a tervbe, valamint mekkora a legnagyobb lehetséges új szoba területe! Bemenet
A haz.be állomány első sorában a tervben meglevő szobák száma (1≤N≤1 000 000), valamint az ház bal felső (FX,FY) és jobb alsó (AX,AY) sarkának koordinátái vannak (0≤FX<AX≤10 000, 0≤FY<AY≤10 000), egy-egy szóközzel elválasztva. A következő N sor mindegyikében egy-egy szoba bal felső (BFXi,BFYi) és jobb alsó (JAXi,JAYi) sarkának koordinátái vannak (FX≤BFXi<JAXi≤AX, FY≤BFYi<JAYi≤AY) egy-egy szóközzel elválasztva. Kimenet
A haz.ki szöveges állomány első sorába a kialakítható új szobák számát kell írni! A második sorba a legnagyobb új szoba területe kerüljön! Példa
| Bemenet |
Kimenet |
5 1 1 10 10
1 1 5 5
6 1 10 2
6 3 9 10
1 6 3 10
4 6 4 10 | 2
8
|
Tesztadatok
Címkék
A feladat forrása: NTOITV 2013, 11-13. évfolyam, döntő
Algoritmusok:
|
|
2004-2016 BDG algoritmus szakkör