Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

GORE - Paz verde! Hipocrisia mundial!

Albert Arnold Gore Jr é o nome completo do ex-vice-presidente dos Estados Unidos, Al Gore, ganhador do prêmio Nobel da Paz de 2007 pelo seu trabalho incessante de conscientizar a população mundial para as mudanças climáticas causadas pelo homem. O documentário "An Inconvenient Truth" vencedor do Oscar, mostra os efeitos causados pelo aquecimento global na paisagem do planeta e prevê um futuro catastrófico para a humanidade se a tendência de usurpar os recursos do planeta não for mudada.

Al Gore cresceu em Washington DC uma vez que seu pai foi deputado e depois senador pelo Tenessee. Graduou-se em Harvard em 1969 e foi um ativista contra a guerra do Vietnam e chegou a apoiar o líder Martin Luther King na sua luta contra a segregação racial. Sua atuação como vice-presidente dos Estados Unidos na administração de Bill Clinton também foi excepcional. Apesar de ter tido mais votos que o concorrente do partido republicano, perdeu as eleições presidenciais e afastou-se da disputa da presidência.

Um dos seus trabalhos mais importantes diz respeito ao posicionamento ótimo de fornos em produção de tijolos. O processo de fabricação de tijolos é bastante poluente, e exige a queima em alta temperatura do barro a fim de que o tijolo atinja a consistência desejada. A queima consome grandes quantidades de madeira, produzida em fazendas para este fim. Estudos da Universidade de Harvard mostram que há uma distância máxima para o posicionamento nesses fornos: se estiverem muito distantes, a dispersão do calor não permite que a queima seja feita por igual, trazendo prejuízos à produção de tijolos e também ao meio ambiente. Uma vez que os fornos são posicionados no meio da floresta (que é cortada para a queima), as distâncias são medidas usando a métrica de Manhattan, ou seja, a distância entre dois pontos é dada pela soma dos valores absolutos das diferenças das coordenadas. Sua tarefa é, dada a localização de vários fornos numa fazenda, e uma distância D, determinar, para cada um dos fornos, quantos fornos estão à distância no máximo D. Com estes dados será possível determinar quais fornos precisam ser acesos simultaneamente sem prejuízos econômico ou ambiental.

Entrada

A primeira linha do caso de testes contém um inteiro I que indica o número de instâncias subsequentes. A primeira linha de cada instância possui dois inteiros N e D (1 ≤ D ≤ 500000, 1 ≤ N ≤ 100000) representando o número de fornos e uma distância, respectivamente. Cada uma das próximas N linhas possui dois inteiros x e y (0 ≤ x, y ≤ 100000) que indicam a posição de um forno.

Saída

Para cada instância imprima uma linha contendo N inteiros que indicam quantos fornos estão à distância no máximo D dos fornos 1, 2, ..., N.

Exemplo de entrada
1
13 2
0 2
1 3
1 2
1 1
2 4
2 3
2 2
2 1
2 0
3 3
3 2
3 1
4 2
Exemplo de saída
4 7 7 7 4 7 12 7 4 7 7 7 4

Adicionado por:Wanderley Guimarăes
Data:2008-10-01
Tempo limite:0.526s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO PERL6 PY_NBC SCALA TCL
Origem:Primeira Seletiva para Maratona de Programacao IME-USP - 2008

hide comments
2012-07-31 13:32:09 Jeferson Lesbão de Siqueira[UNITAU]
Tem um problema bem parecido com esse na IOI de 2007
2012-05-21 15:40:24 Wisllay Vitrio [INF-UFG]
Tem dois detalhes neste enunciado:

1) O limite de D năo é respeitado. NAs entradas utilizadas D pode ir até mais de 300000.

2) Existe um espaço após o último número de cada linha, mas o enunciado năo fala nada a respeito disso. Levei vários WA por causa disso.
2011-12-18 22:33:05 Helder Dias [UNIFEI]
ia falar o mesmo Paulo :P
2011-09-13 16:22:21 Rafael Brandão
A segunda entrada está recebendo um D maior que 250000, que năo está na especificaçăo. :/
2011-05-26 21:36:42 Paulo Sérgio dos Santos Araujo
O que mais me deixou tesudo por essa questăo foi o titulo... Dead Fish Rules! xD
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.