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

SUPERMER - Supermercado

A rede de supermercados BemBom, da cidade de Planalto, decidiu reformular o armazenamento de seus estoques. No sistema atual, cada uma das lojas da rede possui espaço para armazenar um pequeno estoque, sendo freqüentemente necessário transportar mercadorias de uma loja para outra. Para racionalizar o transporte e aumentar a capacidade de estoque, a direção da rede Bem-Bom decidiu instalar um depósito central. De forma a diminuir os custos com transporte, ficou definido que o novo depósito deve ser localizado em um quarteirão que minimize a soma das distâncias dele até todas as lojas da rede.

Por ser uma cidade planejada, Planalto possui uma característica muito peculiar. Todas as suas ruas são orientadas na direção leste-oeste ou norte-sul, e todos os quarteirões são do mesmo tamanho. Veja uma parte do mapa de Planalto na figura abaixo. Os quarteirões em Planalto são identificados pelo número de quadras, em cada direção, que os separam da localização da prefeitura (0,0). Localizações a leste e a norte da prefeitura são identificadas por coordenadas positivas, e localizações a oeste e a sul por coordenadas negativas.

Parte do mapa de Planalto

Tarefa

A sua tarefa é, dadas as coordenadas dos quarteirões onde estão localizados todos os supermercados da rede, determinar o quarteirão onde deve ser instalado o novo depósito. A localização deste depósito deve ser tal que a soma das distâncias entre o depósito e as lojas, em número de quarteirões em ambas as direções, seja a menor possível. A distância entre dois quarteirões é dada pela distância entre eles na direção leste-oeste mais a distância na direção norte-sul. Por exemplo, a distância entre os quarteirões (2,-1) e (4, 3) é 2 + 4 = 6.

Entrada

A entrada é composta de vários conjuntos de teste. A primeira linha de cada conjunto de teste contém um número inteiro S que é o número de supermercados da rede. A seguir, são dadas S linhas, cada uma contendo dois números inteiros X e Y, representando as coordenadas do quarteirão onde se situa um dos supermercados. X representa a coordenada na direção leste-oeste e Y represetna a coordenada na direção norte-sul. O final da entrada é dado por um conjunto de teste com S = 0.

Saída

Para cada conjunto de teste, o seu programa deve escrever três linhas na saída. A primeira linha deve conter um identificador do conjunto de teste, no formato “Teste n”, onde n é numerado seqüencialmente a partir de 1. A segunda linha deve conter as coordenadas X e Y do quarteirão onde deve ser instalado o novo depósito, separadas por um espaço em branco. Se mais de um quarteirão puder ser escolhido como localização do depósito, seu programa pode imprimir qualquer um deles. A terceira linha deve ser deixada em branco. O formato do exemplo de saída abaixo deve ser seguido rigorosamente.

Exemplo

Entrada:
4
1 2
-3 -3
4 -1
-5 0
5
1 3
7 13
25 13
15 14
25 1
0

Saída:
Teste 1
-2 0

Teste 2
15 13

Restrições

0 <= S <= 1000 (S = 0 apenas para indicar o final da entrada)
-1000 <= X <= 1000
-1000 <= Y <= 1000


Adicionado por:Wanderley Guimarăes
Data:2006-05-05
Tempo limite:0.263s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO NODEJS PERL6 PY_NBC SCALA TCL VB.NET
Origem:Olimpiada Brasileira de Informatica 2003

hide comments
2016-04-17 19:08:56 Elsio [UFABC]
Similar ao DENGUE: http://br.spoj.com/problems/DENGUE/
Só que esse é mais fácil pois pode ser resolvido pegando as medianas (não confundir com média) dos eixos.
O Dengue, por ser um grafo com mais de duas dimensões, tem de ser resolvido por desfolhamento
Tem um outro ainda mais difícil que tem que ser resolvido por Floyd Warshall, mas eu não me lembro qual é (spoj não tem categorias como o URI por ex)
2015-11-05 05:16:22 FelipeEcomp
O primeiro exemplo, a saida e -1,0, ja testei aqui e foi aceito. Abraco
2015-11-05 03:21:41
as possíveis saídas do Teste 1 são: (-3,0),(-2,0),(-1,0),(0,0),(1,0),(-3,-1),(-2,-1),(-1,-1),(0,-1),(1,-1)

o Teste 2 só tem uma saída possível que é a mostrada acima
2012-02-12 04:22:07 Fernando Fonseca [ITA]
Se eu contei certo, no Teste 1 tem 10 pontos que podem ser usados como depósito.
2011-10-19 13:18:41 Ivan
no Teste 1 tem 5 pontos diferentes que podem ser como resposta...
Este exemplo foi orrivel...
kk
2011-10-19 12:42:19 Ivan
eu que errei
;)
ta certo o resultado
2011-10-19 11:21:41 Ivan
no teste 1 a saida năo tem como ser (1,0).
e nem (-2,0). Tenq ve isso awe!
2010-03-21 20:47:35 Glauco Buarque
no teste 1, a saida eh: 1 0
2010-01-11 02:50:25 Thiago Stuckert [UNB]
O erro de digitaçăo já foi corrigido!

Last edit: 2010-03-21 00:05:19
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.