FastPrepFastPrep
Problem Brief

Spreading Fire (Intuit India)

INTERNOA

There is a 2D plane of size N*M. There is fire which is there at K different points in the 2D plane. From each of these K points, the fire is spreading in a circular form with the radius of the fire increasing by time. So, if at t=1, the radius of fire (represented by R) was 2, at t=2, it becomes 4, at t=3, it become 6 and so on. "t" denotes time here. Help us determine, the number of points (points are denoted by (x,y), where both x and y are whole numbers, and are within the plane) which would not be touched by the fire.

Input Format

The first line has 3 space separated integer N, M and K, dimensions of the 2D plane and the number of fire points.

Next K lines each having 2 space separated integers, stating the coordinates of the fire.

Next line denotes the R, the radius of the fire at t=1,

Next line contain an integer T, stating the time at which we want to know points not touched by fire.

1Example 1

Input
N = 4, M = 4, K = 2, firePoints = [[1, 1], [3, 3]], R = 1, T = 2
Output
6
Explanation

Fire does not reach these 6 points:

  • 0,3
  • 0,4
  • 1,4
  • 3,0
  • 4,0
  • 4,1

Constraints

Limits and guarantees your solution can rely on.

  • 1 <= N <= 1000
  • 1 <= M <= 1000
  • 1 <= K <= 5
  • 1 <= R <= 10
  • 1 <= T <= 100
public int countSafePoints(int N, int M, int K, int[][] firePoints, int R, int T) {
    // write your code here
}
Input

N

4

M

4

K

2

firePoints

[[1, 1], [3, 3]]

R

1

T

2

Output

6

Sign in to submit your solution.