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
2009-09-02 02:31:51 Murilo Adriano Vasconcelos
Qual a complexidade esperada?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.