Le problème de la fin heureuse (en fait un théorème) déclare que

Tout ensemble de cinq points dans le plan en position générale a un sous-ensemble de quatre points qui forment les sommets d'un quadrilatère convexe.

Le problème a été ainsi nommé par Paul Erdős lorsque deux mathématiciens qui ont d'abord travaillé sur le problème, Ester Klein et George Szekeres, se sont fiancés puis se sont mariés.

Clarifications:

• La position générale ici signifie qu'il n'y a pas trois points colinéaires.

• Le quadrilatère formé par les quatre sommets sera toujours considéré comme non intersecté, quel que soit l'ordre des points. Par exemple, étant donné les quatre points [1 1], [1 2], [2 1], [2 2]le quadrilatère visé est la place, pas le nœud papillon:

  

• Un quadrilatère sans intersection est convexe si aucun angle intérieur ne dépasse 180 degrés; ou de manière équivalente si les deux diagonales se trouvent à l'intérieur du quadrilatère.

Le défi

Étant donné 5 points avec des coordonnées entières positives, affichez 4 de ces points qui forment un quadrilatère convexe.

Règles

S'il existe plusieurs solutions (c'est-à-dire plusieurs ensembles de 4 points), vous pouvez toujours choisir de sortir l'une d'entre elles ou toutes.

Les formats d'entrée et de sortie sont flexibles comme d'habitude (tableaux, listes, liste de listes, chaînes avec des séparateurs raisonnables, etc.).

Code golf, le moins d'octets gagne.

Cas de test

1. Contribution:

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

   Il n'y a qu'une seule sortie possible:

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

2. Contribution:

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

   Il existe cinq solutions:

   [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. Contribution:

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

   Il existe trois solutions:

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

   Pour illustrer, voici les trois solutions à ce cas:

CJam, 37 34 32 octets

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

Je ne sais pas si :-Vc'est assez heureux, mais comme le souligne K Zhang, il y a le =}à la fin. :)

Cela n'imprime qu'une seule solution car la suppression des doublons serait plus coûteuse.

Testez-le ici.

Explication

L'idée est assez simple. Nous générons tous les quadrilatères possibles (y compris tous les ordres des points) et sélectionnons ensuite les convexes. Nous testons la convexité en examinant chaque paire d'arêtes et en vérifiant qu'elles tournent toutes dans la même direction.

Le sens de rotation peut être obtenu assez facilement à partir d'un produit scalaire. Si vous prenez les trois points consécutifs sur un quadrilatère, et tracez des lignes du premier au deuxième et du premier au troisième, puis projetez ce dernier sur la perpendiculaire du premier ... vous obtenez un nombre dont le signe vous indique que ces trois points tournent à gauche ou à droite. (Je devrais probablement ajouter un diagramme pour cela.) Cette "projection sur la perpendiculaire" semble assez impliquée, mais signifie simplement que nous inversons l'un des deux vecteurs et soustrayons les composants après la multiplication au lieu de les ajouter. Voici donc le code ...

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 octets

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

L'entrée se présente sous la forme d'une matrice 2D où les colonnes sont respectivement X et Y:

[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]

Tous les ensembles de 4 points qui créent des quadrilatères convexes sont affichés dans le même format.

Voici une démo légèrement modifiée pour fonctionner avec Octave

Explication

Cette solution prend tous les sous-ensembles de 4 points d'entrée (l'ordre n'a pas d'importance). Pour ce faire, nous créons la matrice d'identité et nier: ~eye(5). Nous parcourons les colonnes de cette matrice et k(l'index de boucle) est un tableau logique qui spécifie lequel des 4 points à considérer. Nous l'utilisons ensuite pour saisir ces 4 points XY de l'entrée ( I(k,:)).

Nous calculons ensuite la coque convexe de ces 4 points ( convhull). La sortie de convhullest les indices de l'entrée qui correspondent aux points qui composent la coque convexe (avec le premier index dupliqué pour fermer la coque).

Pour un quadrilatère convexe, les quatre points feront partie de la coque convexe des mêmes points ( nnz(convhull(points)) > 4). Si nous détectons que c'est le cas, nous affichons les points qui ont été utilisés pour cette itération particulière.

Javascript (ES6), 306 293 283 octets

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)

Explication :

La fonction ccalcule le produit croisé du vecteur entre 3 points adjacents du polygone et renvoie 1 s'il est positif et 0 sinon (remarque: le produit croisé ne peut pas être nul car les points ne peuvent pas être colinéaires).

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)}

La fonction ket jgénère toutes les permutations cycliques (en ignorant l'inversion de l'ordre) du tableau d'entrée.

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])

La fonction «i» est alors appelée pour chaque permutation cyclique pour calculer la somme de la fonction cpour chacun des 4 triplets de coordonnées adjacentes. Si les produits croisés ont tous le même signe, ils seront tous soit 0 ou 1 et totaux à 0 (modulo 4) et le polygone est concave et est poussé dans le tableau de sortie. Si un triplet a un signe différent, le total sera non nul (modulo 4) et le polygone sera convexe.

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

La fonction fest utilisée pour initialiser le tableau de sortie, puis appeler les fonctions ci-dessus avant de renvoyer la sortie.

Tests :

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(','))
    );
  }
);

Modifier :

Peut également gérer des points colinéaires en utilisant la version originale et en changeant les deux premières lignes en:

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))}

Cependant, comme ce cas est spécifiquement exclu dans la question, les caractères supplémentaires ne sont pas nécessaires.

Mathematica 105 96 octets

Select[#~Subsets~{4},f@#&]&sélectionne, dans une liste de (5) points, les sous-ensembles de 4 points qui satisfont f.

fest satisfaite lorsque chaque point, sur les 4 points d'un set, repose sur le RegionBoundarydes ConvexHull4 points.

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

Cas de test

1. Regardons les 5 coques convexes de sous-ensembles (chacun de 4 points) 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}} est la seule solution; chacun des quatre points sert de sommet de la coque convexe (des mêmes 4 points).

{{6, 8}, {1, 10}, {6, 6}, {8, 10}} n'est pas une solution; la coque convexe n'a que 3 sommets. {6, 8} se trouve dans la coque.

Les sous-ensembles restants ne sont pas non plus des solutions:

2. {{4, 8}, {1, 9}, {9, 9}, {10, 2}, {1, 6}} propose trois solutions.

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}} propose 5 solutions.

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

Notez que chacun des cinq points se trouve à la limite de la coque convexe de tous les points.

Si l'un des points est supprimé, les 4 points restants seront chacun des sommets de la coque convexe réduite.