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
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]
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]
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:
Odpowiedzi:
CJam,
373432 bajtyNie jestem pewien, czy
:-V
jest 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 ...
źródło
!}
można też uznać za mrugnięcieMATLAB, 67 bajtów
Dane wejściowe mają postać macierzy 2D, w której kolumnami są odpowiednio X i Y:
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 ik
(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
). Wynikiemconvhull
są 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.źródło
JavaScript (ES6),
306293283 bajtówObjaśnienie :
Funkcja
c
oblicza 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).Funkcja
k
ij
generowanie wszystkich cyklicznych permutacji (ignorowanie odwrócenia kolejności) tablicy wejściowej.Następnie dla każdej cyklicznej permutacji wywoływana jest funkcja „i” w celu obliczenia sumy funkcji
c
dla 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.Funkcja
f
służy do inicjalizacji tablicy wyjściowej, a następnie wywołania powyższych funkcji przed zwróceniem danych wyjściowych.Testy :
Edytuj :
Może także obsługiwać punkty współliniowe przy użyciu oryginalnej wersji i zmieniając pierwsze dwa wiersze na:
Ponieważ jednak ten przypadek jest wyraźnie wykluczony z pytania, dodatkowe znaki nie są konieczne.
źródło
Mathematica
10596 bajtówSelect[#~Subsets~{4},f@#&]&
wybiera z listy (5) punktów te podzbiory 4 punktów, które spełniająf
.f
jest spełniony, gdy każdy punkt, o 4 punkty w zestawie, leży naRegionBoundary
zConvexHull
4 punktów.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}} .
{{{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.
{
{{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ń.
{
{{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.
źródło