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

TIROS - Atirador de elite

Problemas e mais problemas! Assim foi a Seletiva para Maratona de Programação dos Alunos do IME-USP. Enquanto o big-boss “Guima” conquistava o Egito, seus seguidores passavam muito sufoco e angústia durante a prova. Assim que retornou, Guima conversou com os alunos e as principais reclamações foram: a demora nas respostas e os estouros repentinos dos balões. Muitos alunos eram bichos (alunos do primeiro ano . . . hehe) e estavam com muito medo de ter perdido o problema. Eles realmente achavam que era preciso fazer tudo do zero para ganhar um novo balão.

Imediatamente, após a reunião, o grande Faraó Guima pediu as fitas de segurança do laboratório, e constatou que havia um atirador de elite no canto da sala. Em intervalos de tempo o atirador disparava um tiro contra os balões. Após assistir ao vídeo inteiro, Guima percebeu que o atirador sempre dava um tiro que estourava a maior quantidade de balões possível.

Agora, o grande Cacique Guima quer que você e sua equipe escrevam um programa que dadas N coordenadas (x, y), determine o número de balões que o atirador consegue acertar com um único tiro. Um fato importante é que as balas do atirador não fazem curva.

Entrada

A entrada é composta por diversas instâncias. A primeira linha da entrada contém um inteiro T indicando o número de instâncias.

Cada instância é composta de diversas linhas. A primeira linha de cada instância contém um inteiro N — o número de balões. Seguido por N linhas que descrevem N coordenadas de balões. Cada coordenada de balão é dada por dois inteiros x e y separados por um espaço.

Restrições

1 <= N <= 1000
-100000 <= x,y <= 100000
Dois balões quaisquer não possuem as mesmas coordenadas.

Saída

Para cada instância imprima o número de balões que o atirador consegue acertar com um tiro.

Exemplo de entrada

2
9
0 0
1 1
1 2
1 3
2 1
2 2
2 3
3 2
3 3
5
1 1
2 1
3 1
4 1
3 2

Saída para o exemplo de entrada

4
4

Adicionado por:Wanderley Guimarăes
Data:2009-08-31
Tempo limite:2.541s
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:Segunda Seletiva para Maratona de Programacao IME-USP - 2008

hide comments
2012-03-24 15:17:10 tcomp
ATENCAO:
A Bateria de testes desse problema é falha, só considera tg = 0, 45, 90, -90 e -45 graus
2012-02-26 01:41:00 Juan [UFES]
limite de T?
2012-02-21 07:55:40 Ivan
6h pra conseguir... n fico 100%, mas ficou... puta trampo meu! tive q tentar de 12019301 de modos
2011-04-25 04:16:50 Wyllian
Leonardo: "A primeira linha da entrada contém um inteiro T indicando o número de instâncias."
2009-11-11 17:48:01 LEONARDO PIRES RUBIM [ UNIPAMPA ALEGRETE ]
qual é o final da entrada, não é especificado no problema?
2009-09-10 03:12:30 Bobby - Eletricista [UDESC]
mistake


Last edit: 2009-09-10 03:30:47
2009-09-03 23:49:51 Arnett [UFCG]
Nuss! Como aquele bixo conseguiu passar em tão pouco tempo?! O algoritmo dele deve ser linear O.o'
2009-09-02 20:48:33 Alessandro Ferreira - UFMS
Há um jeito simples de se resolver esse problema em n^2?
2009-09-02 04:40:07 Murilo Adriano Vasconcelos
A minha năo chega a ser nł e năo passou =|
Aliás, passou sim!

Last edit: 2012-03-24 16:37:53
2009-09-02 03:47:05 gogo40
Eu passei com uma solução O(N² log N)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.