Stwierdza to szczęśliwy problem zakończenia (właściwie twierdzenie)

Każdy zestaw pięciu punktów na płaszczyźnie w pozycji ogólnej ma podzbiór czterech punktów, które tworzą wierzchołki wypukłego czworoboku.

Problem został tak nazwany przez Paula Erdősa, kiedy dwóch matematyków, którzy najpierw pracowali nad tym problemem, Ester Klein i George Szekeres, zaręczyli się, a następnie pobrali.

Wyjaśnienia:

• Ogólna pozycja tutaj oznacza, że ​​żadne trzy punkty nie są współliniowe.

• Czworobok utworzony przez cztery wierzchołki zawsze będzie uważany za nie przecinający się, niezależnie od kolejności punktów. Na przykład, biorąc pod uwagę cztery punkty [1 1], [1 2], [2 1], [2 2]zamierzone czworokąt jest kwadratem, a nie Muszka:

  

• Nie przecinający się czworobok jest wypukły, jeśli kąt wewnętrzny nie przekracza 180 stopni; lub równoważnie, jeśli obie przekątne leżą wewnątrz czworoboku.

Wyzwanie

Biorąc pod uwagę 5 punktów o dodatnich współrzędnych całkowitych, należy wyprowadzić 4 z tych punktów, które tworzą wypukły czworobok.

Zasady

Jeśli istnieje kilka rozwiązań (kilka zestawów po 4 punkty), możesz konsekwentnie wybierać jeden lub wszystkie z nich.

Formaty wejściowe i wyjściowe są elastyczne jak zwykle (tablice, listy, lista list, ciągi znaków z rozsądnymi separatorami itp.).

Code golf, najmniej bajtów wygrywa.

Przypadki testowe

1. Wkład:

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

   Możliwe jest tylko jedno wyjście:

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

2. Wkład:

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

   Istnieje pięć rozwiązań:

   [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. Wkład:

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

   Istnieją trzy rozwiązania:

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

   Aby to zilustrować, oto trzy rozwiązania tego przypadku:

CJam, 37 34 32 bajty

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

Nie jestem pewien, czy :-Vjest wystarczająco szczęśliwy, ale jak zauważa K Zhang, jest =}na końcu. :)

Spowoduje to wydrukowanie tylko jednego rozwiązania, ponieważ usunięcie duplikatów byłoby droższe.

Sprawdź to tutaj.

Wyjaśnienie

Pomysł jest dość prosty. Generujemy wszystkie możliwe czworokąty (w tym wszystkie uporządkowania punktów), a następnie wybieramy wypukłe. Testujemy wypukłość, patrząc na każdą parę krawędzi i sprawdzając, czy wszystkie obracają się w tym samym kierunku.

Sens zwrotu można dość łatwo uzyskać z iloczynu punktowego. Jeśli weźmiesz trzy kolejne punkty na czworoboku i narysujesz linie od pierwszego do drugiego, i od pierwszego do trzeciego, a następnie rzucisz ten drugi na prostopadły do ​​pierwszego ... otrzymujesz liczbę, której znak mówi ci czy te trzy punkty skręcają w lewo czy w prawo. (Prawdopodobnie powinienem dodać do tego schemat.) To „rzutowanie na prostopadłą” jest dość wciągające, ale tak naprawdę oznacza tylko, że odwracamy jeden z dwóch wektorów i odejmujemy składniki po pomnożeniu zamiast dodawać je. Oto kod ...

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 bajtów

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

Dane wejściowe mają postać macierzy 2D, w której kolumnami są odpowiednio X i 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]

Wszystkie zestawy 4 punktów, które tworzą wypukłe kwadraty, są wyświetlane w tym samym formacie.

Oto wersja demonstracyjna, która jest nieco zmodyfikowana do pracy z Octave

Wyjaśnienie

To rozwiązanie przyjmuje wszystkie podzbiory 4 punktów wejścia (kolejność nie ma znaczenia). Aby to zrobić, możemy utworzyć macierz tożsamości i neguje go: ~eye(5). Pętlimy przez kolumny tej macierzy i k(indeks pętli) jest logiczną tablicą, która określa, który z 4 punktów należy wziąć pod uwagę. Następnie używamy tego, aby pobrać te 4 punkty XY z input ( I(k,:)).

Następnie obliczamy wypukły kadłub z tych 4 punktów ( convhull). Wynikiem convhullsą wskaźniki wejściowe, które odpowiadają punktom tworzącym wypukły kadłub (z pierwszym indeksem zduplikowanym w celu zamknięcia kadłuba).

W przypadku wypukłego czworokąta wszystkie cztery punkty będą częścią wypukłego kadłuba tych samych punktów ( nnz(convhull(points)) > 4). Jeśli wykryjemy, że tak jest, wyświetlamy punkty, które zostały użyte do tej konkretnej iteracji.

JavaScript (ES6), 306 293 283 bajtów

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)

Objaśnienie :

Funkcja coblicza iloczyn krzyżowy wektora między 3 sąsiadującymi punktami wielokąta i zwraca 1, jeśli jest dodatni, a w przeciwnym razie 0 (uwaga: iloczyn krzyżowy nie może być zerowy, ponieważ punkty nie mogą być współliniowe).

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

Funkcja ki jgenerowanie wszystkich cyklicznych permutacji (ignorowanie odwrócenia kolejności) tablicy wejściowej.

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

Następnie dla każdej cyklicznej permutacji wywoływana jest funkcja „i” w celu obliczenia sumy funkcji cdla każdej z 4 trojaczków sąsiednich współrzędnych. Jeśli wszystkie produkty krzyżowe mają ten sam znak, wówczas wszystkie będą miały wartość 0 lub 1 i łącznie będą miały wartość 0 (moduł 4), a wielokąt jest wklęsły i zostanie wypchnięty do tablicy wyjściowej. Jeśli jakakolwiek tryplet ma inny znak, wówczas suma będzie różna od zera (moduł 4), a wielokąt będzie wypukły.

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

Funkcja fsłuży do inicjalizacji tablicy wyjściowej, a następnie wywołania powyższych funkcji przed zwróceniem danych wyjściowych.

Testy :

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

Edytuj :

Może także obsługiwać punkty współliniowe przy użyciu oryginalnej wersji i zmieniając pierwsze dwa wiersze na:

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

Ponieważ jednak ten przypadek jest wyraźnie wykluczony z pytania, dodatkowe znaki nie są konieczne.

Mathematica 105 96 bajtów

Select[#~Subsets~{4},f@#&]&wybiera z listy (5) punktów te podzbiory 4 punktów, które spełniają f.

fjest spełniony, gdy każdy punkt, o 4 punkty w zestawie, leży na RegionBoundaryz ConvexHull4 punktów.

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

Przypadki testowe

1. Spójrzmy na 5 wypukłych kadłubów podzbiorów (każdy z 4 punktów) {{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}} to jedyne rozwiązanie; każdy z czterech punktów służy jako wierzchołek wypukłego kadłuba (tych samych 4 punktów).

{{6, 8}, {1, 10}, {6, 6}, {8, 10}} nie jest rozwiązaniem; wypukły kadłub ma tylko 3 wierzchołki. {6, 8} leży w kadłubie.

Pozostałe podzestawy również nie są rozwiązaniami:

2. {{4, 8}, {1, 9}, {9, 9}, {10, 2}, {1, 6}} ma trzy rozwiązania.

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}} ma 5 rozwiązań.

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

Zauważ, że każdy z pięciu punktów leży na granicy wypukłego kadłuba wszystkich punktów.

Jeśli jeden z punktów zostanie usunięty, pozostałe 4 punkty będą wierzchołkami zmniejszonego wypukłego kadłuba.