Coast Guard.Of late, smuggling has increased many fold and as Chief of the Coast Guard,

0 votes
asked Aug 9, 2018 by Gokul

Of late, smuggling has increased many fold and as Chief of the Coast Guard, you are responsible for intercepting the smuggling vessels and nullify them. You have stationed several smart, high speed boats in the sea. The entire sea under your control can be divided into a rectangular grid of 1 km by 1 km squares. Due to a design flaw in the boats, they can move only in horizontal or vertical directions (EW or NS) (they cannot move diagonally, in particular). Of course, no two boats are stationed in the same grid square.

The boats can reach an adjacent grid square (horizontally or vertically) in one minute. Every grid square that can be reached by one boat faster than it can be reached by any other boat is said to be controlled by that boat. If a grid square may be reached by at least one more boat in the same time as the fastest boat, it is said to be uncontrolled.

It is in your interest to minimize the number of grid squares that are uncontrolled.

In the figure above we are considering a grid of 3 rows and four columns. The bottom left corner square is numbered (0,0), and the top right corner is numbered (3,2). Two boats are in positions (2,0) and (0,2). The four shaded squares can be reached in equal (minimum) time by both boats, and are hence uncontrolled.

Given the position of the boats, write a program to identify the number of grid squares that are uncontrolled.


0<M,N<50, 1<k<10

Input Format

The first line will be three comma separated integers M, N and kM and N give the number of rows and columns of the grid, and k the number of boats.

The next k lines will a pair of comma separated numbers giving the coordinates of the grid square with a boat


A single line containing the number of uncontrolled grid squares.


Example 1








M=3,N=4,k=2. There are 3 rows and 4 columns. There are 2 boats at (2,0) and (0,2).

The position is the same as in the earlier figure. There are 4 uncontrolled squares. Hence the result is 4.

Example 2








M=2, N=4, k=2. There are two boats positioned as below

It can be seen that there is no grid square that is reached at the same minimum time from the two boats. Hence the result is 0.

Your answer

Your name to display (optional):
Privacy: Your email address will only be used for sending these notifications.
Anti-spam verification:
To avoid this verification in future, please log in or register.
Welcome to OnlineGDB Q&A, where you can ask questions related to programming and OnlineGDB IDE and and receive answers from other members of the community.