ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1168. Radio Stations

Time limit: 1.0 second
Memory limit: 64 MB
Along the surface of Romania, there are K radio stations positioned at different points and altitudes. Each of these radio stations has a given broadcast radius, that is, the maximum distance it can send its signal to. The government wants to place a radio receiver somewhere on the map, so that it will receive the signals from all the K radio stations: this means that the distance to every radio station should be less or equal to the broadcast radius of that radio station.
The map of Romania is given as a M*N matrix, where the value in row i and column j represents the altitude of the corresponding zone. The side of a square in this matrix is 1. All the K radio stations are placed at distinct coordinates on the map and at the same height as the corresponding zone (plus, they are placed exactly in the center of their square). The radio receiver can be placed in the center of any square not occupied by a radio station, at the same altitude of the square or it can be placed higher with an integer number of meters. The radio receiver cannot be placed in a square occupied by a radio station.
Your task is to decide how many possibilities to place the radio receiver the government has. Note that if the radio receiver may be placed in row i and column j at altitudes h1 and h2 (h1 ≠ h2), this counts as 2 different possibilities.


The first line of input contains 3 integers: M, N (1 ≤ M, N ≤ 50) and K (1 ≤ K ≤ min(M*N-1, 1000)), representing the dimensions of the map and the number of radio stations. Next there are M lines each containing N integers, which are the altitudes of the zones on the map (no altitude will be higher than 32000 or lower than 0). After that, there will be K lines, each containing 3 numbers: i, j and R. i and j will be the location of the radio station on the map and R will be its broadcast radius (R is a real number, not larger than 100000 and not less than 0).
No two radio stations will be placed on the same square.


You should output one integer number, which is the total number of valid possibilities to place the radio receiver on the map.


5 5 3
1 2 3 4 5
6 7 8 9 10
1 2 3 4 5
6 7 8 9 10
5 4 3 2 1
1 1 4.3
5 5 4.3
5 1 4.3


The radio receiver can be placed at position (3, 2), with extra height 0 and extra height 1, and at position (3, 3), with extra height 0 and extra height 1. So, there are 4 possible ways to place the receiver.
When you compute distances, be aware that they are distances in a 3D space.
Problem Author: Mugurel Ionut Andreica
Problem Source: Romanian Open Contest, December 2001