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.|

TARZAN12 - Tarzan

Tarzan vive na floresta e é o responsável por manter a ordem na região onde vive. Para locomover-se entre as árvores ele só usa cipós pois esse é um meio de transporte muito mais rápido e seguro do que andar no chão da selva, além de, é claro, poder soltar seu grito característico enquanto viaja.

Os cipós das árvores têm todos o mesmo alcance. Dessa forma, é possível viajar de cipó de uma árvore para outra se a distância entre elas é no máximo D, onde D é o alcance dos cipós.

Recentemente uma forte chuva assolou a região e derrubou algumas árvores, restando na floresta apenas N árvores. Agora Tarzan quer saber se ele consegue viajar de cipó entre todas árvores remanescentes para poder continuar mantendo a ordem na região.

Para poder manter a ordem ele precisa ser capaz de, partindo de qualquer uma das árvores, poder chegar a todas as outras árvores remanescentes, possivelmente passando por outras árvores no caminho, sempre utilizando somente cipós.

Entrada

A primeira linha da entrada contém dois inteiros, N e D, indicando respectivamente o número de árvores remanescentes e o alcance dos cipós. Cada uma das N linhas seguintes contém dois inteiros Xi e Yi, as coordenadas da i-ésima árvore. Não existem duas árvores com as mesmas coordenadas.

Saída

Seu programa deve escrever uma única linha, contendo um único caractere: 'S' se Tarzan consegue viajar de cipó entre todas as árvores remanescentes, e 'N' caso contrário.

Restrições

  • 2 ≤ N ≤ 1000
  • 1 ≤ D ≤ 5000
  • 0 ≤ XiYi ≤ 5000

Exemplos

Entrada
4 5
1 1
6 1
6 6
11 6

Saída
S

Entrada
4 5
1 1
6 6
11 6
13 8

Saída
N


Adicionado por:Edmundo Rodrigues
Data:2014-05-26
Tempo limite:1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:ADA95 ASM32 GAWK BASH BF C CSHARP C++ 4.3.2 CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN GO HASK ICON ICK JAVA JS-RHINO LUA NEM NICE NODEJS OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON PYTHON3 RUBY SCM guile SCM qobi SED ST WHITESPACE
Origem:Olimpíada Brasileira de Informática 2012 - Nível 2 - Fase 1

hide comments
2016-10-14 06:32:02
Eu ganho 100 pontos de 100 no judge da própria OBI, mas aqui da que tá ultrapassando o tempo limite (é o mesmo tanto aqui quanto no judge da OBI). Segue meu código, que com certeza dá pra otimizar (ainda mais por causa do meu nested loop), se puderem ajudar... Obrigado!
https://gist.github.com/pxpc2/17714569bf4c32bb987f98c0f7d5636c
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.