Programmeringsolympiadens final 2019

Start

2019-01-18 08:10 UTC

Programmeringsolympiadens final 2019

End

2019-01-18 13:10 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -323 days 12:00:08

Time elapsed

5:00:00

Time remaining

0:00:00

Problem E
Skogsbrand

En skogsbrand har brutit ut i heltalsskogen! Heltalsskogen består av ett oändligt stort tvådimensionellt plan där ett träd finns på varje punkt med heltalskoordinater. Just nu brinner $N$ av dessa träd. Varje minut sprider sig elden från varje brinnande träd till dess fyra grannar (träden omedelbart norr, öster, väster och söder). För att stoppa brandens framfart har brandkåren huggit ner $M$ träd. Ett nedhugget träd kan inte börja brinna, så dessa punkter fungerar som en slags vägg. Du är intresserad av att räkna ut hur stor skada branden kommer att orsaka. Om $T$ minuter kommer ett stort regnväder släcka hela branden. Därför vill du veta hur många träd som brinner efter $T$ minuter.

Indata

Första raden innehåller tre heltal:

  • antalet brinnande träd $N$ ($1 \leq N \leq 100$),

  • antalet nedhuggna träd $M$ ($0 \leq M \leq 100$),

  • och antalet minuter till det stora regnvädret $T$ ($0 \leq T \leq 10^9$).

De följande $N$ raderna innehåller två heltal $x_ i,y_ i$ ($0 \leq x_ i, y_ i < 10^5$), koordinater för de brinnande träden.

De följande $M$ raderna innehåller två heltal $x_ i,y_ i$ ($0 \leq x_ i, y_ i < 10^5$), koordinater för de nedhuggna träden.

Inga två träd, oavsett om de är brinnande eller nedhuggna, kommer ligga på samma koordinater.

Utdata

Skriv ut ett heltal, antalet träd som brinner efter $T$ minuter.

Poängsättning

Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Grupp

Poängvärde

Gränser

$1$

$5$

$N = 1$, $M = 0$

$2$

$9$

$T \leq 100$, $M = 0$, $x_ i, y_ i < 100$

$3$

$10$

$T \leq 400$, $x_ i, y_ i < 100$

$4$

$11$

$M = 0$, $x_ i, y_ i < 100$

$5$

$21$

$x_ i, y_ i < 100$

$6$

$15$

$M = 0$

$7$

$29$

Inga ytterligare begränsningar

Förklaring av exempelfall

I exempel $1$ sprider sig elden till $(0,2)$, $(1,3)$ och $(2,2)$. Totalt är det alltså $4$ brinnande träd.

I exempel $2$ är det enda brinnande trädet omringat av nedhuggna träd. Det blir alltså bara ett brinnande träd, trots att $T$ är så stort.

I exempel $3$ hinner inte elden sprida sig eftersom $T = 0$, så svaret blir $4$.

Sample Input 1 Sample Output 1
1 1 1
1 2
1 1
4
Sample Input 2 Sample Output 2
1 4 12345678
2 2
1 2
2 1
2 3
3 2
1
Sample Input 3 Sample Output 3
4 1 0
1 1
1 2
2 3
3 4
7 7
4
Sample Input 4 Sample Output 4
1 2 100000
0 0
2 1
1 2
20000199999