ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Romanian Open Contest December 2001

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

B. Radio Stations

Ограничение времени: 1.0 секунды
Ограничение памяти: 64 МБ
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
4

Замечания

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.
Автор задачи: Mugurel Ionut Andreica
Источник задачи: Romanian Open Contest, December 2001
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1168. Radio Stations