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

ZELDA - Onde está Zelda

O mundo de Hyrule está em perigo mais uma vez, e Link, novamente, está tentando salvá-lo. Para tal, Link precisa se encontrar com a princesa Zelda, para que ela possa lhe ajudar com seus grandes poderes místicos. Quando se encontrarem, Link e Zelda, juntos, irão derrotar o mal de uma vez por todas.

Link sabe que Zelda está sendo mantida refém dentro de algum dos N templos de Hyrule. Se Hyrule for projetada em um plano cartesiano, um templo consiste em um retângulo cujos lados são paralelos aos eixos.

Infelizmente, Link não sabe em qual templo Zelda está sendo mantida. Entretanto, sua espada tem uma habilidade especial (chamada Dowsing) que permite a Link saber a direção e o sentido em que Zelda está, a partir de sua própria localização.

A figura abaixo, que representa o segundo exemplo da entrada, exemplifica a situação. A espada de Link indica que Zelda está na direção e sentido do vetor destacado em preto. Logo, Link sabe que Zelda está em algum lugar sobre o segmento pontilhado.

zelda

Sua tarefa é fornecer a Link a lista dos templos nos quais Zelda pode estar. Note que, se Zelda estiver sobre alguma borda (aresta ou vértice) de um templo, então considera-se que ela está dentro dele (note que, no exemplo, Zelda pode estar na Water Temple).

Entrada

Cada caso de teste começa com uma linha contendo um inteiro N (1 ≤ N ≤ 100), o número de templos em Hyrule. A segunda linha contém dois inteiros xL e yL (0 ≤ xL, yL ≤ 103), as coordenadas da localização de Link. A terceira linha contém dois inteiros xD e yD (-103xD, yD ≤ 103) indicando o vetor da direção indicada pela espada de Link.

As próximas N linhas contém, cada uma, a descrição de um templo. Cada templo é descrito com uma linha contendo nome, x1, y1, x2 e y2. nome é uma string com 1 a 20 letras maiúsculas ou minusculas, indicando o nome do templo. O par (x1,y1) e o par (x2, y2) indicam as coordenadas de vértices opostos do templo (0 ≤ x1 < x2 ≤ 103 e 0 ≤ y1 < y2 ≤ 103).

É garantido que:

  • O vetor de direção não é nulo (isto é, (xD,yD) ≠ (0,0));
  • A lista de templos em que Zelda pode estar não é vazia;
  • Link não está dentro de nenhum templo;
  • Não há interseção entre nenhum par de templos.

A entrada termina com N = 0.

Saída

Para cada caso de teste, imprima uma linha com os nomes dos templos nos quais Zelda pode estar. Imprima os nomes na ordem em que são apresentados na entrada, separados por espaços (mas não imprima um espaço depois do último nome).

Examplo

Entrada:
2
4 6
3 0
DodongoCavern 2 2 5 4
JabuJabusBelly 7 4 10 8
4
14 10
-1 1
WaterTemple 1 15 6 18
ForestTemple 10 3 17 8
FireTemple 9 11 12 16
GreatDekuTree 3 2 7 4
0 Saída: JabuJabusBelly
WaterTemple FireTemple

Adicionado por:Ricardo Oliveira [UFPR]
Data:2014-06-07
Tempo limite:1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:8o Contest Noturno

hide comments
2016-12-14 16:25:20


Last edit: 2016-12-15 01:56:22
2016-04-29 19:27:05 Vinícius Brito
Já submeti várias vezes o código e juro que não encontro erro nele...
2014-06-11 16:56:40 Diogo Soares [UFAM]
Eu havia interpretado um detalhe errado msm, AC agora. vlw
2014-06-11 16:41:32 Ricardo Oliveira [UFPR]
O enunciado descreve os casos em que Zelda está em um templo. Os limites das coordenadas inteiras também săo dados.
2014-06-11 16:11:24 Diogo Soares [UFAM]
Há algum caso de teste especial? Usei intersecçăo entre retas, mas estou pegando WA. Há algum problema com precisăo ou outro detalhe?

Last edit: 2014-06-11 16:32:25
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.