Županijsko natjecanje 2011. godine za 3. i 4. razred Srednje Škole - 3. zadatak

Gradska uprava jednog malog grada odlučila je izgraditi ugostiteljski objekt u obližnjoj park-šumi. S obzirom da u park-šumi ima popriličan broj stabala, nastaju dva problema: gdje izgraditi novi ugostiteljski objekt i kolike površine treba biti.

Da ne bi nepotrebno sjekli stabla, i da bi udovoljili narodu, poručili su svim stanovnicima grada da se izjasne po tom pitanju. Stanovnici moraju na papir zapisati gdje bi oni smjestili ugostiteljski objekt i koliki bi površine bio taj ugostiteljski objekt.

Park-šuma je pravokutnog oblika i podijeljena je na jedinične kvadrate. Na svakom od kvadrata se može, a i ne mora nalaziti jedno stablo. Ugostiteljski objekt je također pravokutnog oblika, rubova paralelnih s rubovima park šume.

Stanovnici šalju prijedloge s koordinatama i dimenzijama ugostiteljskog objekta, i to u zapisu X, Y, H i W. Gdje su X i Y koordinate gornjeg lijevog ugla objekta, a W i H širina i visina objekta.

Kako je popriličan broj stanovnika poslao prijedloge, gradska vlast vas je zamolila za pomod. Za svaki od prijedloga trebate izračunati broj stabala koji se nalazi unutar pojedinog pravokutnika, tj. predložene parcele za gradnju ugostiteljskog objekta. Gradska vlast uzet de na razmatranje samo one prijedloge koji zahtjevaju minimalnu sječu stabala. Nakon toga, gradska vlast može odlučiti gdje izgraditi ugostiteljski objekt, ali tako da posijeku što manje stabala.

ULAZNI PODACI

U prvom retku nalaze se dva prirodna broja R i S ( 1 ≤ R,S ≤ 1000 ), visina i širina park šume.

U slijededih R redaka se nalazi po S znakova. Znak 'S' označava da se na tom mjestu nalazi stablo, a znak '.' (točka) označava da se na tom mjestu nalazi prazno mjesto.

U sljededem retku nalazi se jedan prirodni broj N ( 1 ≤ N ≤ 100,000 ), koji predstavlja broj prijedloga stanovnika.

U sljededih N redaka nalaze se po četiri prirodna broja X, Y, H i W koji predstavljaju koordinate i-tog predloženog ugostiteljskog objekta i njegove dimenzije.

IZLAZNI PODACI

Ispisati broj prijedloga koji zahtjevaju minimalnu sječu stabala.

PRIMJERI TEST PODATAKA

ulaz

3 3
.S.
...
...
1
1 1 3 3

izlaz

1

ulaz

4 4
S..S
S.S.
..SS
SSSS
2
1 1 2 3
4 4 1 1

izlaz

1

ulaz

4 2
S.
S.
..
..
2
2 1 2 2
1 1 1 1

izlaz

2

Objašnjenje

Objašnjenje drugog test primjera: Prva slika je sama park šuma, a druge dvije predstavljaju dva predložena pravokutnika za izgradnju ugostiteljskog objekta. Prvi prijedlog zahtjeva sječu tri stabla, dok drugi zahtjeva sječu samo jednog stabla. Dakle postoji samo jedan prijedlog koji ima minimalan broj posječenih stabala (samo jedno stablo)