O problema do final feliz (na verdade um teorema) afirma que

Qualquer conjunto de cinco pontos no plano na posição geral possui um subconjunto de quatro pontos que formam os vértices de um quadrilátero convexo.

Paul Erdős nomeou o problema quando dois matemáticos que primeiro trabalharam no problema, Ester Klein e George Szekeres, ficaram noivos e depois se casaram.

Esclarecimentos:

• A posição geral aqui significa que não há três pontos colineares.

• O quadrilátero formado pelos quatro vértices será sempre considerado como sem interseção, independentemente da ordem dos pontos. Por exemplo, dado os quatro pontos [1 1], [1 2], [2 1], [2 2]o quadrilátero pretendido é a praça, não o arco-tie:

  

• Um quadrilátero sem interseção é convexo se nenhum ângulo interior exceder 180 graus; ou equivalente se as duas diagonais estiverem dentro do quadrilátero.

O desafio

Dados 5 pontos com coordenadas inteiras positivas, produza 4 desses pontos que formam um quadrilátero convexo.

Regras

Se houver várias soluções (ou seja, vários conjuntos de 4 pontos), você poderá escolher consistentemente a saída de uma delas ou todas.

Os formatos de entrada e saída são flexíveis como de costume (matrizes, listas, lista de listas, seqüências de caracteres com separadores razoáveis, etc.).

Código de golfe, menos bytes ganha.

Casos de teste

1. Entrada:

   [6 8] [1 10] [6 6] [5 9] [8 10]
   

   Existe apenas uma saída possível:

   [6 8] [1 10] [6 6] [5 9]
   

2. Entrada:

   [3 8] [7 5] [6 9] [7 8] [5 1]
   

   Existem cinco soluções:

   [3 8] [7 5] [6 9] [7 8]
   [3 8] [7 5] [6 9] [5 1]
   [3 8] [7 5] [7 8] [5 1]
   [3 8] [6 9] [7 8] [5 1]
   [7 5] [6 9] [7 8] [5 1]
   

3. Entrada:

   [4 8] [1 9] [9 9] [10 2] [1 6]
   

   Existem três soluções:

   [4 8] [1 9] [10 2] [1 6]
   [4 8] [9 9] [10 2] [1 6]
   [1 9] [9 9] [10 2] [1 6]
   

   Para ilustrar, aqui estão as três soluções para este caso:

CJam, 37 34 32 bytes

{e!Wf<{2*3ew{)f.-~W%.*:-V>},!}=}

Não tenho certeza se :-Vestá feliz o suficiente, mas como K Zhang aponta, há =}o final. :)

Isso imprime apenas uma solução, pois a remoção de duplicatas seria mais cara.

Teste aqui.

Explicação

A ideia é bastante simples. Geramos todos os quadriláteros possíveis (incluindo todos os pedidos dos pontos) e, em seguida, apenas selecionamos os convexos. Testamos a convexidade observando cada par de arestas e verificando se todos estão girando na mesma direção.

O sentido de viragem pode ser obtido facilmente de um produto escalar. Se você pegar os três pontos consecutivos em um quadrilátero e desenhar linhas do primeiro ao segundo e do primeiro ao terceiro, e depois projetar o último na perpendicular do primeiro ... você obtém um número cujo sinal indica se esses três pontos viram à esquerda ou à direita. (Eu provavelmente deveria adicionar um diagrama para isso.) Essa "projeção na perpendicular" parece bastante envolvida, mas na verdade significa apenas que invertemos um dos dois vetores e subtraímos os componentes após a multiplicação, em vez de adicioná-los. Então aqui está o código ...

e!       e# Generate all permutations of the five input points.
Wf<      e# Discard the fifth point in each permutations, giving all
         e# possible quadrilaterals.
{        e# Select the first for which this block gives a truthy result...
  2*     e#   Double the list of points, so that it includes each cyclically
         e#   adjacent set of three points.
  3ew    e#   Get all sublists of length 3, i.e. all sets of three consecutive
         e#   points (with two duplicates).
  {      e#   Filter these sets of three points...
    )    e#     Pull off the last point.
    f.-  e#     Subtract it from the other two, giving vectors from it to
         e#     to those.
    ~    e#     Unwrap the array dumping both vectors on the stack.
    W%   e#     Reverse one of them.
    .*   e#     Element-wise multiplication.
    :-   e#     Subtract the second element from the first. This completes
         e#     the projection.
    V>   e#     Check whether it's greater than 0. This is *false* for right-
         e#     turning sets of three points.
  },     e#   If all corners are right-turning, this will result
         e#   in an empty array.
  !      e#   Logical NOT - hence, only quadrilaterals where all corners
         e#   are right-turning give something truthy.
}=

MATLAB, 67 bytes

I=input('');for k=~eye(5);if nnz(convhull(I(k,:)))>4;I(k,:),end;end

A entrada está na forma de uma matriz 2D em que as colunas são X e Y, respectivamente:

[6 8; 1 10; 6 6; 5 9; 8 10]
[3 8; 7 5; 6 9; 7 8; 5 1]
[4 8; 1 9; 9 9; 10 2; 1 6]

Todos os conjuntos de 4 pontos que criam quadriláteros convexos são exibidos no mesmo formato.

Aqui está uma demonstração que é ligeiramente modificada para funcionar com o Octave

Explicação

Esta solução utiliza todos os subconjuntos de 4 pontos da entrada (a ordem não importa). Para fazer isso, criamos a matriz identidade e negá-lo: ~eye(5). Percorremos as colunas dessa matriz e k(o índice do loop) é uma matriz lógica que especifica qual dos 4 pontos a considerar. Em seguida, usamos isso para obter esses 4 pontos XY da entrada ( I(k,:)).

Em seguida, calculamos o casco convexo desses 4 pontos ( convhull). A saída de convhullsão os índices da entrada que correspondem aos pontos que compõem o casco convexo (com o primeiro índice duplicado para fechar o casco).

Para um quadrilátero convexo, todos os quatro pontos farão parte do casco convexo dos mesmos pontos ( nnz(convhull(points)) > 4). Se detectarmos que esse é o caso, exibiremos os pontos que foram usados ​​para essa iteração específica.

Javascript (ES6), 306 293 283 bytes

c=(v,w,x)=>(w[0]-v[0])*(w[1]-x[1])-(w[1]-v[1])*(w[0]-x[0])>0?1:0
i=(v,w,x,y)=>(c(v,w,x)+c(w,x,y)+c(x,y,v)+c(y,v,w))%4==0&&r.push([v,w,x,y])
j=(v,w,x,y)=>{i(v,w,x,y);i(v,w,y,x);i(v,x,w,y)}
k=(v,w,x,y,z)=>{j(v,w,x,y);j(v,w,x,z);j(v,w,y,z);j(v,x,y,z);j(w,x,y,z)}
f=(v)=>(r=[],k(...v),r)

Explicação :

A função ccalcula o produto cruzado do vetor entre 3 pontos adjacentes do polígono e retorna 1 se for positivo e 0 caso contrário (nota: o produto cruzado não pode ser zero, pois os pontos não podem ser co-lineares).

j=(v,w,x,y)=>{i(v,w,x,y);i(v,w,y,x);i(v,x,w,y)}
k=(v,w,x,y,z)=>{j(v,w,x,y);j(v,w,x,z);j(v,w,y,z);j(v,x,y,z);j(w,x,y,z)}

A função ke jgera todas as permutações cíclicas (ignorando a reversão da ordem) da matriz de entrada.

i=(v,w,x,y)=>(c(v,w,x)+c(w,x,y)+c(x,y,v)+c(y,v,w))%4==0&&r.push([v,w,x,y])

A função 'i' é então chamada para cada permutação cíclica para calcular a soma da função cpara cada um dos 4 trigêmeos de coordenadas adjacentes. Se todos os produtos cruzados tiverem o mesmo sinal, serão todos 0 ou 1 e totalizarão 0 (módulo 4) e o polígono é côncavo e é empurrado para a matriz de saída. Se qualquer trigêmeo tiver um sinal diferente, o total será diferente de zero (módulo 4) e o polígono é convexo.

f=(v)=>(r=[],k(...v),r)

A função fé usada para inicializar a matriz de saída e, em seguida, chamar as funções acima antes de retornar a saída.

Testes :

c=(v,w,x)=>(w[0]-v[0])*(w[1]-x[1])-(w[1]-v[1])*(w[0]-x[0])>0?1:0
i=(v,w,x,y)=>(c(v,w,x)+c(w,x,y)+c(x,y,v)+c(y,v,w))%4==0&&r.push([v,w,x,y])
j=(v,w,x,y)=>{i(v,w,x,y);i(v,w,y,x);i(v,x,w,y)}
k=(v,w,x,y,z)=>{j(v,w,x,y);j(v,w,x,z);j(v,w,y,z);j(v,x,y,z);j(w,x,y,z)}
f=(v)=>(r=[],k(...v),r)

tests = [
  [[6,8],[1,10],[6,6],[5,9],[8,10]],
  [[3,8],[7,5],[6,9],[7,8],[5,1]],
  [[4,8],[1,9],[9,9],[10,2],[1,6]]
];

tests.forEach(
  (test,i)=>{
    console.log( "Test " + (i+1) );
    f(test).forEach(
      (x)=>console.log( "  " + x.map((e)=>"("+e[0]+","+e[1]+")").join(','))
    );
  }
);

Editar :

Também pode manipular pontos co-lineares usando a versão original e alterando as duas primeiras linhas para:

t=(a,b,c)=>Math.sign((b[0]-a[0])*(b[1]-c[1])-(b[1]-a[1])*(b[0]-c[0]))
p=(a,b,c,d)=>[t(a,b,c),t(b,c,d),t(c,d,a),t(d,a,b)].filter(x=>x).reduce((p,c,i,a)=>p&c==a[0],1)
q=(a,m,n,o)=>[a[0],a[m],a[n],a[o]]
f=(a)=>{r=[];for(i=0;i<5;i++){b=a.slice();b.splice(i,1);r.push(q(b,1,2,3));r.push(q(b,1,3,2));r.push(q(b,2,1,3))}return r.filter((a)=>p(...a))}

No entanto, como esse caso é especificamente excluído na pergunta, os caracteres extras não são necessários.

Mathematica 105 96 bytes

Select[#~Subsets~{4},f@#&]&seleciona, de uma lista de (5) pontos, os subconjuntos de 4 pontos que satisfazem f.

festá satisfeito quando cada ponto, dos 4 pontos em um jogo, encontra-se no RegionBoundaryda ConvexHulldos 4 pontos.

f@p_:=Apply[And,RegionBoundary@ConvexHullMesh@p~RegionMember~#&/@p];
Select[#~Subsets~{4},f@#&]&

Casos de teste

1. Vejamos os 5 cascos convexos dos subconjuntos (cada um de 4 pontos) de {{6, 8}, {1, 10}, {6, 6}, {5, 9}, {8, 10}} .

Select[#~Subsets~{4},f@#&[{{6, 8}, {1, 10}, {6, 6}, {5, 9}, {8, 10}}]

{{{6, 8}, {1, 10}, {6, 6}, {5, 9}}}

{{6, 8}, {1, 10}, {6, 6}, {5, 9}} é a única solução; cada um dos quatro pontos serve como um vértice do casco convexo (dos mesmos 4 pontos).

{{6, 8}, {1, 10}, {6, 6}, {8, 10}} não é uma solução; o casco convexo possui apenas 3 vértices. 6, 8 está dentro do casco.

Os subconjuntos restantes também não são soluções:

2. {{4, 8}, {1, 9}, {9, 9}, {10, 2}, {1, 6}} tem três soluções.

Select[#~Subsets~{4},f@#&[{{4, 8}, {1, 9}, {9, 9}, {10, 2}, {1, 6}}]

{
{{4, 8}, {1, 9}, {10, 2}, {1, 6}},
{{4, 8}, {9, 9}, {10, 2}, {1, 6 }},
{{1, 9}, {9, 9}, {10, 2}, {1, 6}}
}

3. {{3, 8}, {7, 5}, {6, 9}, {7, 8}, {5, 1}} tem 5 soluções.

Select[#~Subsets~{4},f@#&[{{3, 8}, {7, 5}, {6, 9}, {7, 8}, {5, 1}}]

{
{{3, 8}, {7, 5}, {6, 9}, {7, 8}},
{{3, 8}, {7, 5}, {6, 9}, {5, 1 }},
{{3, 8}, {7, 5}, {7, 8}, {5, 1}},
{{3, 8}, {6, 9}, {7, 8}, {5 , 1}},
{{7, 5}, {6, 9}, {7, 8}, {5, 1}}
}

Observe que cada um dos cinco pontos fica no limite do casco convexo de todos os pontos.

Se qualquer um dos pontos for removido, os 4 pontos restantes serão vértices do casco convexo reduzido.