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

MAPAS - Mapas do Gugo

A internet oferece uma variedade de facilidades interativas para mapas, de tal forma que os usuários podem ter uma visão geral de uma região geográfica ou podem fazer zoom para uma rua específica ou mesmo um prédio específico, em um mapa mais detalhado. Por exemplo, a Unicamp pode aparecer em um mapa de Campinas com um certo nível de detalhes, ou em um mapa de Barão Geraldo com mais detalhes.

Gugo comprou uma grande coleção de mapas retangulares e deseja criar um serviço para processar seqüências de consultas em mapas com vários níveis de detalhes. As localidades são representadas por um par de coordenadas inteiras (x, y). Os mapas têm identificadores únicos e são representados por dois pares de coordenadas, descrevendo cantos opostos do mapa. Os lados de todos os mapas são paralelos aos eixos cartesianos padrão x e y. Um mapa abrange todas as localidades contidas no retângulo, incluindo as que estão sobre a borda.

O nível de detalhe de um mapa pode ser estimado pelo tamanho da área retangular representada pelo mapa: um mapa que cobre uma área menor contém informações mais detalhadas e portanto maior nível de detalhe.

Pode haver sobreposição das áreas cobertas pelos mapas. Se uma consulta é feita para uma localidade presente em dois ou mais mapas, o mapa preferido é o de maior nível de detalhe. Em caso de empate, o preferido é o mapa em que a localidade é mais próxima do centro do mapa. Finalmente, se ainda houver empate, o mapa preferido é o de menor identificador.

Tarefa

Dados o conjunto de mapas e uma lista de consultas de localidades você deve escrever um programa que determine, se existir, o mapa com o maior nível de detalhe para cada uma das consultas.

Entrada

A entrada é composta de vários conjuntos de testes. A primeira linha de um conjunto de testes contém dois inteiros M, e R, separados por um espaço em branco, que indicam respectivamente o número de mapas (1 <= M <= 30000) e o número de consultas (1 <= R <= 50000). Cada uma das M linhas seguintes contém cinco inteiros I, X1, Y1, X2, Y2, separados por um espaço em branco; I representa o identificador do mapa (1 <= I <= M ), (X1, Y1) representa a coordenada do canto inferior esquerdo do mapa, e (X2, Y2) representa a coordenada do canto superior direito do mapa (−10000 <= X1 < X2 <= 10000 e −10000 <= Y1 < Y2 <= 10000). Muitos dos mapas (mesmo de áreas disjuntas) têm cantos com coordenadas x ou y coincidentes. O número máximo de cantos de mapas com coordenadas x não coincidentes é 500, e o número máximo de cantos de mapas com coordenadas y não coincidentes também é 500. As R linhas seguintes contêm as consultas. Cada consulta é dada em uma linha contendo dois inteiros XR e YR, representando uma localidade (−10000 <= XR <= 10000 e −10000 <= YR <= 10000). O final da entrada é indicado por M = R = 0.

Saída

Para cada conjunto de teste da entrada seu programa deve produzir a saída da seguinte forma. A primeira linha deve conter um identificador do conjunto de teste, no formato ‘Teste n’, onde ‘n’ é numerado seqüencialmente a partir de 1. Para cada consulta do conjunto de testes da entrada seu programa deve imprimir uma linha, contendo um inteiro N, representando o mapa preferido para a localidade, se existir. Se não existir mapa para a localidade desejada imprima o valor zero. A última linha deve ser deixada em branco. A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente.

Exemplo

Entrada:
2 4
1 1 1 4 5
2 3 2 7 8
4 2
5 3
6 9
2 2
4 4
4 1 -3 4 2
2 -3 -4 2 -1
3 -4 -2 -1 3
1 -2 1 3 4
0 0
2 -3
1 3
-2 1
0 0

Saída:
Teste 1
1
2
0
1

Teste 2
0
2
1
3

Restrições

1 <= M <= 30000 (M = 0 para indicar final da entrada)
1 <= N <= 50000 (N = 0 para indicar o final da entrada)
-10000 <= X1 < X2 <= 10000
-10000 <= Y1 < Y2 <= 10000


Adicionado por:Wanderley Guimarăes
Data:2008-04-03
Tempo limite:1s-2.929s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST WHITESPACE
Origem:Olimpíada Brasileira de Informática 2005 -- Seletiva 2

hide comments
2011-03-10 00:35:41 Jorge Augusto C. dos Reis
Só dá erro no teste 10... affff
2011-03-10 00:32:59 Jorge Augusto C. dos Reis
Preciso de mais casos de teste...
Tudo certo e meus teste, mas dá erro

Existe alguma sutileza ou 'problema' com esse problema que năo estou considerando.

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.