MRAVOGRA - Mravograd

no tags 

The hard working ants have built a town called Ant Town. They modeled their town after Manhattan, with H horizontal and V vertical streets which cross in V×O intersections. As ants don't like water, with the first raindrops comes chaos in Ant Town. Town authorities have placed umbrellas under which any number of ants can hide, but only on N intersections.

When the rain starts, each ant on an intersection starts running, using streets, to the nearest intersection with an umbrella. But, if an ant can choose from more than one such intersection, it panics and, not knowing where to go, stays on its starting intersection and gets wet. Town authorities use the name "wet intersections" for such starting intersections.

For example, if Ant Town has 10 horizontal and 10 vertical streets, and if there are 4 intersections with umbrellas, then the question marks in the figure represent "wet intersections":

Picture represents first example. We count streets from left to right from 1 to V and from down upwards from 1 to H.

Write a program which, given the locations of intersections with umbrellas, determines the number of "wet intersections" in Ant Town.


The first line contains two integers H and V (1 ≤ H, V ≤ 30 000), the numbers of horizontal and vertical streets in Ant Town.

Horizontal streets are numbered 1 to H, vertical streets 1 to V.

The second line contains an integer N (1 ≤ N ≤ 10), the number of intersections with umbrellas.

Each of the following N lines contains two integer h and v, meaning that there is an umbrella on the crossing of horizontal street h and vertical street v. The locations of all umbrellas will be distinct.


Output the number of "wet intersections" in Ant Town.


10 10
4 4
4 6
6 4
9 9



9 9
2 2
5 5
8 8



100 100
50 50
50 51


hide comments
linkret: 2016-03-22 21:52:52

Wonder what the 0.00 solution is...

:D: 2011-05-09 05:32:48

Test cases are correct. You can check them using trivial O(H*V*N) brute force algo. Use the same approach to generate your own test cases.

Edit, visualization for second case:

Last edit: 2011-05-09 05:46:37
V0iD!: 2011-05-06 07:19:03

is the output for 2nd test case correct? shouldn't it be 34?
and could someone give more test cases pls?? thanks..

Last edit: 2011-05-06 07:30:20

Added by:Stjepan Glavina
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Croatian National 2007