uCoder | 1095 | Nível: 7 | Tempo Limite: 10
O incidente de Sverdlovsk
Adaptado por Erich Rodrigues
Competição: USP - Seletiva para Maratona de Programação, 2013
Durante os anos da União Soviética o nome da cidade de Ecaterimburgo era Sverdlovsk, em homenagem ao bolchevique Iakov Sverdlov, filho de um artesão judeu que era excelente orador e foi um dos principais protagonistas ao lado de Lenin na revolução de outubro de 1905. Era considerado honesto, enérgico e trabalhador e respeitado por todos os setores do partido. Faleceu aos 34 anos. A cidade retomou o nome original em 1991 por iniciativa de Boris Yeltsin primeiro presidente da Rússia, nascido na cidade.
Em 2 de abril de 1979, quando a cidade ainda se chamava Sverdlovsk houve um vazamento de antraz de uma fábrica militar na cidade. Este incidente é muitas vezes chamado de “Chernobyl biológico”, e causou aproximadamente 100 mortes, apesar de que o número exato de vítimas e contaminados seja desconhecido. A União Soviética negou por anos as reais causas do acidente e todos os registros das vítimas desapareceram, pois poderiam revelar sérias violações da Convenção
de Armas Biológicas.
As autoridades soviéticas tiveram de recorrer a procedimentos altamente sofisticados de descontaminação, especialmente das áreas rurais. Cada área retangular de dimens˜oes N por M metros era dividida em N ×M setores quadrados de um metro quadrado. Estes setores eram identificados pelas coordenadas de seus centros, numeradas de oeste para leste e de sul para norte a partir de (1, 1).
Cada setor seria considerado descontaminado se ele for coberto por pelo menos K agentes de saúde. Cada agente era capaz de cobrir uma área circular. O raio dessa área variava de acordo com os equipamentos usados e com a experiência do agente de saúde. Sua tarefa é determinar quantos desses setores são considerados descontaminados, isso é, cobertos por pelo menos K agentes. Consideramos que um setor é coberto se seu centro está numa área coberta por um agente de saúde.
Entrada
A entrada é composta por diversas instâncias e termina com final de arquivo (EOF).
A primeira linha de cada instância contém dois inteiros, N e M , indicando a dimensão da área retangular falada no enunciado. A segunda linha contém o número de agentes, C, e o número K. As C linhas seguintes têm a descrição dos agentes Xc , Yc e Rc , onde (Xc , Yc ) é o centro da área circular de raio Rc que o agente cobre.
A entrada deve ser lida da entrada padrão.
Saída
Para cada instância imprima o número de setores que são cobertos por pelo menos K agentes.
A saída deve ser escrita na saída padrão.
Restrições
• 1 ≤ N ≤ 10^3
• 1 ≤ M ≤ 10^5
• 1 ≤ K ≤ C ≤ 10^3
• 1 ≤ Xc ≤ N
• 1 ≤ Yc ≤ M
• 0 ≤ Rc ≤ 10^8
Observação
Mais precisamente, um setor com centro (xs , ys ) é coberto por um agente posicionado em (xa , ya )
capaz de descontaminar uma área com raio r se
| Exemplo de Entrada | Exemplo de Saída |
|---|---|
|
10 10 |
26 |