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