NézetNyomtat

Parcellák (Megoldás)
Címkék > Feladat

Parcellák

Alacsony Áron földműves szeretné felosztani megművelendő termőföldjét oly módon, hogy minden egyes veteményét egy különálló parcellán tudja termeszteni. A földosztás sosem volt az erőssége: egyszerre mindig csak egy kijelölt téglalap alakú parcellát tud négy, ugyancsak téglalap alakú részre osztani úgy, hogy a négy rész közé egységnyi szélességű sétányokat iktat be a közlekedés megkönnyítése végett.


Egy felosztást a keletkező részparcellák választóvonalainak metszéspontjával jellemzünk. Ezek a metszéspontok sohasem lehetenek korábban létrehozott választóvonalakon, de ugyanakkor előfordulhat, hogy egy metszéspont egy parcella szélén jön létre. Ekkor természetszerűleg csak kétfelé osztjuk a parcellát, de ilyenkor is két plusz sétány keletkezik. Sarokban elhelyezett metszéspontok a parcellák minkét oldalát egységnyi hosszúsággal csökkentik. Speciális esetben egy $1\times 1$-es méretű parcella megszűnik a felosztás után.

Feladat

Írj programot, amely a termőföld méretei és a felosztások adatai alapján megmondja, hogy mekkora a legnagyobb megmaradt parcella.

Bemenet

A PARCELLAK.BE szöveges állomány első sorában a földterület N hosszúsága $(1\le N\le 10000)$ és M szélessége $(1\le M\le 10000)$, valamint a földosztások K száma $(1\le K\le 1000)$. A következő K sor az egyes felosztások adatait tartalmazza, minden egyes sorban két szám szóközzel elválasztva szerepel. Ezek a számok, mint koordináták (oszlop, sor) a felosztás utáni parcellák választóvonalainak metszéspontjait jelölik ki.

Kimenet

A PARCELLAK.KI szöveges állományba az így kapott legnagyobb parcella méretét kell kiírni.

Példa

PARCELLAK.BE PARCELLAK.KI
10 10 5
1 1
2 3
6 2
8 7
10 10
15

Tesztadatok