Elástico
Por 
Brazil
Por Brazil
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.
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.
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 ( 2 ≤ N ≤ 200) (N = 0 apenas para indicar o final da entrada) , 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 (1 ≤ X ≤ 1000 ) e Y (1 ≤ Y ≤ 1000) 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.
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 Entrada | Exemplo de Saída |
|
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 |
Teste 1 5 Teste 2 8 |