Das Happy-End-Problem (eigentlich ein Theorem) besagt das

Jede Menge von fünf Punkten in der Ebene an allgemeiner Position hat eine Teilmenge von vier Punkten, die die Eckpunkte eines konvexen Vierecks bilden.

Das Problem wurde von Paul Erdős so benannt, als sich die beiden Mathematiker Ester Klein und George Szekeres verlobten und heirateten.

Klarstellungen:

• Allgemeine Position bedeutet hier, dass keine drei Punkte kollinear sind.

• Das von den vier Eckpunkten gebildete Viereck wird unabhängig von der Reihenfolge der Punkte immer als nicht schneidend betrachtet. Zum Beispiel, da die vier Punkte [1 1], [1 2], [2 1], [2 2]ist das beabsichtigte Viereck der Platz, nicht die Fliege:

  

• Ein sich nicht schneidendes Viereck ist konvex, wenn kein Innenwinkel 180 Grad überschreitet. oder gleichwertig, wenn beide Diagonalen im Viereck liegen.

Die Herausforderung

Bei 5 Punkten mit positiven Ganzzahlkoordinaten werden 4 Punkte ausgegeben, die ein konvexes Viereck bilden.

Regeln

Wenn es mehrere Lösungen gibt (dh mehrere Sätze mit 4 Punkten), können Sie durchgehend eine oder alle ausgeben.

Eingabe- und Ausgabeformate sind wie gewohnt flexibel (Arrays, Listen, Listenlisten, Zeichenfolgen mit angemessenen Trennzeichen usw.).

Code Golf, gewinnt die wenigsten Bytes.

Testfälle

1. Eingang:

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

   Es gibt nur eine mögliche Ausgabe:

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

2. Eingang:

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

   Es gibt fünf Lösungen:

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

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

   Es gibt drei Lösungen:

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

   Zur Veranschaulichung sind hier die drei Lösungen für diesen Fall:

CJam, 37 34 32 Bytes

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

Ich bin mir nicht sicher, ob :-Vich glücklich genug bin, aber wie K Zhang betont, gibt es =}das Ende. :)

Dies gibt nur eine Lösung aus, da das Entfernen von Duplikaten teurer wäre.

Teste es hier.

Erläuterung

Die Idee ist ziemlich einfach. Wir generieren alle möglichen Vierecke (einschließlich aller Anordnungen der Punkte) und wählen dann nur die konvexen aus. Wir testen die Konvexität, indem wir jedes Kantenpaar untersuchen und prüfen, ob sich alle in die gleiche Richtung drehen.

Der Drehsinn kann ziemlich leicht von einem Skalarprodukt erhalten werden. Wenn Sie die drei aufeinanderfolgenden Punkte auf einem Viereck nehmen und Linien vom ersten zum zweiten und vom ersten zum dritten Punkt zeichnen und dann den letzteren auf die Senkrechte des ersteren projizieren, erhalten Sie eine Zahl, deren Vorzeichen Ihnen sagt ob diese drei Punkte nach links oder rechts drehen. (Ich sollte dafür wahrscheinlich ein Diagramm hinzufügen.) Dieses "Projizieren auf die Senkrechte" klingt ziemlich kompliziert, bedeutet aber eigentlich nur, dass wir einen der beiden Vektoren umkehren und die Komponenten nach der Multiplikation subtrahieren, anstatt sie zu addieren. Also hier ist der 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 Bytes

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

Die Eingabe erfolgt in Form einer 2D-Matrix mit den Spalten X und 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]

Alle Sätze von 4 Punkten, die konvexe Vierecke erzeugen, werden im gleichen Format angezeigt.

Hier ist eine Demo , die leicht modifiziert wurde, um mit Octave zu arbeiten

Erläuterung

Diese Lösung nimmt alle Teilmengen von 4 Punkten der Eingabe (Reihenfolge spielt keine Rolle). Dazu schaffen wir die Identitätsmatrix und negieren es: ~eye(5). Wir durchlaufen die Spalten dieser Matrix und k(der Schleifenindex) ist ein logisches Array, das angibt, welcher der 4 Punkte berücksichtigt werden soll. Wir verwenden dies dann, um diese 4 XY-Punkte von der Eingabe ( I(k,:)) zu erfassen .

Wir berechnen dann die konvexe Hülle dieser 4 Punkte ( convhull). Die Ausgabe von convhullsind die Indizes der Eingabe, die den Punkten entsprechen, aus denen die konvexe Hülle besteht (wobei der erste Index dupliziert wird, um die Hülle zu schließen).

Bei einem konvexen Viereck sind alle vier Punkte Teil der konvexen Hülle derselben Punkte ( nnz(convhull(points)) > 4). Wenn wir feststellen, dass dies der Fall ist, zeigen wir die Punkte an, die für diese bestimmte Iteration verwendet wurden.

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)

Erklärung :

Die Funktion cberechnet das Kreuzprodukt des Vektors zwischen 3 benachbarten Punkten des Polygons und gibt 1 zurück, wenn es positiv ist, und ansonsten 0 (Hinweis: Das Kreuzprodukt kann nicht null sein, da die Punkte nicht kolinear sein können).

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

Die Funktion kund jgenerieren alle zyklischen Permutationen (ohne Umkehrung der Reihenfolge) des Eingabearrays.

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

Die Funktion 'i' wird dann für jede zyklische Permutation aufgerufen, um die Summe der Funktionen cfür jedes der 4 Tripletts benachbarter Koordinaten zu berechnen . Wenn die Kreuzprodukte alle das gleiche Vorzeichen haben, sind sie alle entweder 0 oder 1 und summieren sich zu 0 (Modulo 4), und das Polygon ist konkav und wird in das Ausgabearray verschoben. Wenn ein Triplett ein anderes Vorzeichen hat, ist die Summe ungleich Null (Modulo 4) und das Polygon ist konvex.

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

Die Funktion fwird verwendet, um das Ausgabearray zu initialisieren und dann die obigen Funktionen aufzurufen, bevor die Ausgabe zurückgegeben wird.

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

Bearbeiten :

Kann auch mit kolinearen Punkten umgehen, wenn die ursprüngliche Version verwendet wird und die ersten beiden Linien folgendermaßen geändert werden:

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

Da dieser Fall in der Frage jedoch ausdrücklich ausgeschlossen ist, sind die zusätzlichen Zeichen nicht erforderlich.

Mathematica 105 96 Bytes

Select[#~Subsets~{4},f@#&]&Wählt aus einer Liste von (5) Punkten die Teilmengen von 4 Punkten aus, die erfüllt sind f.

fwenn jeder Punkt erfüllt ist, der 4 Punkte in einem Satz, liegt auf der RegionBoundaryvon der ConvexHullder 4 Punkte.

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

Testfälle

1. Betrachten wir die 5 konvexen Hüllen von Teilmengen (jeweils 4 Punkte) von {{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}} ist die einzige Lösung. Jeder der vier Punkte dient als Scheitelpunkt der konvexen Hülle (mit den gleichen 4 Punkten).

{{6, 8}, {1, 10}, {6, 6}, {8, 10}} ist keine Lösung. Der konvexe Rumpf hat nur 3 Eckpunkte. {6, 8} liegt im Rumpf.

Die übrigen Teilmengen sind ebenfalls keine Lösungen:

2. {{4, 8}, {1, 9}, {9, 9}, {10, 2}, {1, 6}} hat drei Lösungen.

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}} hat 5 Lösungen.

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

Beachten Sie, dass jeder der fünf Punkte an der Grenze der konvexen Hülle aller Punkte liegt.

Wenn einer der Punkte entfernt wird, sind die verbleibenden 4 Punkte jeweils Eckpunkte der reduzierten konvexen Hülle.