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

ELASTICO - Elástico

Este é o nome sugestivo de um jogo muito comum entre um grupo de crianças (todos filhos de professores de geometria). Para este jogo, as crianças utilizam uma prancha retangular de madeira, na qual uma tachinha é fixa no canto inferior esquerdo. Uma borrachinha elástica é amarrada nessa tachinha. As crianças então pregam várias outras tachinhas espalhadas pelo espaço restante. O objetivo do jogo é formar, com a borrachinha, um polígono convexo com pelo menos 3 vértices (tachinhas). Ganha o jogo quem formar o polígono com o maior número de vértices.

Um exemplo de configuração vencedora

Tarefa

Você deve implementar um programa que, dada uma instância do jogo, determine o número de vértices da melhor solução possível.

Entrada

A entrada é composta de vários conjuntos de teste. A primeira linha de cada conjunto de teste contém um número inteiro N (2 <= N <= 200), que indica o número de tachinhas pregadas no pedaço de madeira. A seguir, são dadas N linhas, cada uma contendo dois números inteiros X e Y que representam a posição de uma tachinha em coordenadas cartesianas com relação à tachinha presa no canto inferior esquerdo, considerada a origem do sistema de coordenadas. O final da entrada é dado por um conjunto de teste com N = 0. Você pode assumir que não existem duas tachinhas com as mesmas coordenadas e que não existem três tachinhas alinhadas (na mesma reta) dentro de uma mesma instância do problema.

Exemplo de Entrada
6
4 3
2 2
2 4
3 2
3 1
1 5
8
10 8
3 9
2 8
2 3
9 2
9 10
10 3
8 10
0

Saída

Para cada conjunto de teste 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 o número de vértices da melhor solução para a instância dada. A terceira linha deve ser deixada em branco. O formato do exemplo de saída abaixo deve ser seguido rigorosamente.

Exemplo de Saída
Teste 1
5

Teste 2
8

(esta saída corresponde ao exemplo de entrada acima)

Restrições

2 <= N <= 200 (N = 0 apenas para indicar o final da entrada)
1 <= X <= 1000
1 <= Y <= 1000


Adicionado por:Wanderley Guimarăes
Data:2007-03-03
Tempo limite:1s
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 - Seletiva

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