tło

Wypukłe kadłuba od skończonej liczby punktów to najmniejszy wielokąt wypukły, który zawiera wszystkie punkty, albo jako wierzchołków lub we wnętrzu. Aby uzyskać więcej informacji, zobacz to pytanie dotyczące PGM, które definiuje je bardzo dobrze .

Wejście

N+1Współrzędne 2-D ( N >= 3) przekazywane STDIN(przy dozwolonych innych typowych danych golfowych) w następującym formacie (liczba miejsc po przecinku może się różnić, ale można założyć, że pozostaje ona „rozsądna”, a każda liczba może być reprezentowana jako liczba zmiennoprzecinkowa):

0.00;0.00000
1;0.00
0.000;1.0000
-1.00;1.000000

Wynik

Prawdziwa wartość drukowana na STDOUT(lub równoważna), jeśli pierwszy punkt na liście ( (0.00;0.00000)w powyższym przykładzie) znajduje się w wypukłym kadłubie pozostałych N punktów, a wartość fałszowania w przeciwnym razie.

To jest golf golfowy , więc wygrywa najkrótsze rozwiązanie w bajtach.

• Przypadki graniczne : możesz zwrócić dowolną wartość (ale nie upaść), jeśli punkt leży na granicy wypukłego kadłuba (tj. Na boku lub w wierzchołku na zewnętrznej granicy kadłuba), ponieważ jest to zerowe prawdopodobieństwo zdarzenie (przy jakimkolwiek rozsądnym prawdopodobieństwie).

• Zabronione : cokolwiek (język, operator, struktura danych, wbudowane lub pakiet), które istnieje tylko w celu rozwiązania problemów geometrycznych (np. ConvexHull Mathematica ). Dozwolone są narzędzia matematyczne ogólnego zastosowania (wektory, macierze, liczby zespolone itp.).

Testy

• Powinien zwrócić TRUE: spiralTest1-TRUE , squareTest1-TRUE
• Powinny zwrócić FALSE: spiralTest2-FALSE , squareTest2-FALSE

JOT, 40 39 34 bajty

3 :'(o.1)<(>./-<./)12 o.y*+{.y'@:-

Anonimowa funkcja dyadyczna, przyjmująca punkt, p , jako jeden z jego argumentów, oraz listę punktów, P , jako drugi argument (nie ma znaczenia, który argument jest który), i zwracająca 0lub 1, jeśli p jest poza lub wewnątrz wypukłej z P , odpowiednio. Punkt p i punkty w P są traktowane jako liczby zespolone.

Przykład

  is_inside =: 3 :'(o.1)<(>./-<./)12 o.y*+{.y'@:-

  0.5j0.5  is_inside  0j0 0j1 1j0 1j1
1
  1.5j0.5  is_inside  0j0 0j1 1j0 1j1
0

lub...

Python 2, funkcja, 121 103, pełny program, 162

Python 3, 149 bajtów

import sys,cmath as C
p,q,*P=[complex(*eval(l.replace(*";,")))for l in sys.stdin]
A=[C.phase((r-p)/(q-p+(q==p)))for r in P]
print(max(A)-min(A)>C.pi)

Pobiera dane wejściowe, w tym samym formacie co oryginalny post, za pośrednictwem STDIN i drukuje wartość logiczną wskazującą, czy p znajduje się w wypukłym kadłubie P

Wyjaśnienie

Testy programu, czy różnica pomiędzy maksymalną i minimalną (znakiem) kąty pomiędzy każdym punkcie R na P , P , i stałym dowolnego punktu P na P (po prostu wykorzystać pierwszy punkt P ) jest mniejszy niż 180 °. Innymi słowy, sprawdza, czy wszystkie punkty w P są zawarte w kącie 180 ° lub mniejszym, wokół p . p znajduje się w wypukłym kadłubie P wtedy i tylko wtedy, gdy ten warunek jest fałszywy.

Kosztem kilku kolejnych bajtów możemy zastosować podobną metodę, która nie wymaga od nas jawnego obliczania kątów: Zwróć uwagę, że powyższy warunek jest równoważny z twierdzeniem, że p znajduje się poza wypukłym kadłubem P wtedy i tylko wtedy, gdy istnieje linia od l do p , tak że wszystkie punkty w P znajdują się po tej samej stronie l . Jeśli taka linia istnieje, istnieje również taka linia, która pada na jeden (lub więcej) punktów w P (możemy obracać l, aż dotknie jednego z punktów w P ).

Do (roboczo) znaleźć tę linię, zaczniemy pozwalając l być linia przez p , a pierwszy punkt P . Następnie iterujemy pozostałe punkty w P ; jeśli jeden z punktów znajduje się na lewo od l (zakładamy, że kierunkowość w całym, lewy lub prawy nie ma znaczenia), zastępujemy l linią przechodzącą przez p i ten punkt i kontynuujemy. Po iteracji po całym P , jeśli (i tylko jeśli) p znajduje się poza wypukłym kadłubem, wówczas wszystkie punkty w P powinny znajdować się na prawo od (lub na) l . Sprawdzamy to za pomocą drugiego przejścia nad punktami w P..

Python 2, 172 bajty

import sys
P=[eval(l.replace(*";,"))for l in sys.stdin]
x,y=P.pop(0)
C=lambda(a,b),(c,d):(a-x)*(d-y)-(b-y)*(c-x)>0
l=reduce(lambda*x:x[C(*x)],P)
print any(C(l,q)for q in P)

Alternatywnie, aby zrobić to samo w jednym przejściu, pozwól, aby po lewej stronie znajdowała się rzeczywistość między dowolnymi dwoma punktami q i r , w P , tak że q znajduje się na lewo od r, jeśli q jest na lewo linii przechodzącej przez p i r . Należy pamiętać, że do-lewej z jest relacją zamówienie na P wtedy i tylko wtedy, gdy wszystkie punkty P są na tej samej stronie pewnej linii przechodzącej przez p , to znaczy, jeśli p jest poza wypukłą kadłuba P . Procedura opisana powyżej znajduje minimalny punkt w P.wrt ten porządek, czyli „skrajnie lewą” punkt P . Zamiast wykonywać dwa przejścia, możemy znaleźć maksimum (tj. „Skrajnie prawy” punkt), a także minimum, punkty w P wrt tej samej kolejności w jednym przejściu i sprawdzić, czy minimum znajduje się po lewej stronie maksimum, tzn. faktycznie, to, że po lewej stronie jest przechodnie.

Działa to dobrze, jeśli p znajduje się poza wypukłym kadłubem P , w którym to przypadku z lewej strony jest tak naprawdę relacja rzędna, ale może się zepsuć, gdy p znajduje się wewnątrz wypukłego kadłuba (na przykład spróbuj dowiedzieć się, co będzie się stało, gdyby zabrakło tego algorytmu, gdzie punkty P są wierzchołkami pięciokąta foremnego, działa w kierunku przeciwnym do ruchu wskazówek zegara, a p . jest jego centrum) Aby uwzględnić, że nieznacznie zmienić algorytm: Wybieramy punkt Q na P , a Przepoławiana P wzdłuż linii przechodzącej przez p i q (tzn. Dzielimy P wokół qwrt do-the-left-of.) Mamy teraz „lewą część” i „prawą część” P , każda zawarta w półpłaszczyźnie, tak że z lewej strony jest relacja porządkowa na każdej z nich; znajdujemy minimum lewej części i maksimum prawej części i porównujemy je jak opisano powyżej. Oczywiście nie musimy fizycznie przecinać P , możemy po prostu sklasyfikować każdy punkt w P , szukając minimum i maksimum, w jednym przejściu.

Python 2, 194 bajtów

import sys
P=[eval(l.replace(*";,"))for l in sys.stdin]
x,y=P.pop(0)
C=lambda(a,b),(c,d):(a-x)*(d-y)-(b-y)*(c-x)>0
l=r=P[0]
for q in P:
 if C(P[0],q):l=q*C(l,q)or l
 elif C(q,r):r=q
print C(l,r)

Oktawa, 82 72 bajty

d=dlmread(0,";");i=2:rows(d);~isna(glpk(i,[d(i,:)';~~i],[d(1,:)';1]))&&1

Chodzi o sprawdzenie, czy program liniowy min {c'x: Ax = b, e'x = 1, x> = 0} ma rozwiązanie, w którym e jest wektorem wszystkich, kolumny A są współrzędnymi chmura punktów, a b jest punktem testowym, a c jest dowolne. Innymi słowy, próbujemy przedstawić b jako wypukłą kombinację kolumn A.

Aby uruchomić skrypt, użyj octave -f script.m <input.dat

R, 207 bajtów

d=read.csv(file("stdin"),F,";")
q=function(i,j,k)abs(det(as.matrix(cbind(d[c(i,j,k),],1))))
t=function(i,j,k)q(i,j,k)==q(1,i,j)+q(1,i,k)+q(1,j,k)
any(apply(combn(2:nrow(d),3),2,function(v)t(v[1],v[2],v[3])))

Skrypt pobiera dane wejściowe ze STDIN, np Rscript script.R < inputFile.

Generuje wszystkie trójkąty z Nostatnich punktów (ostatniej linii apply(combn(...) i sprawdza, czy pierwszy punkt znajduje się w trójkącie za pomocą tfunkcji.

tużywa metody area, aby zdecydować, czy Ujest w ABC: (pisanie (ABC)dla obszaru ABC) Ujest w ABCiff (ABC) == (ABU) + (ACU) + (BCU). Również obszary są obliczane za pomocą wzoru determinującego (patrz tutaj, aby zobaczyć ładne demo z Wolfram).

Podejrzewam, że to rozwiązanie jest bardziej podatne na błędy numeryczne niż moje inne, ale działa na moich testach.

R, 282 bajtów

d=read.csv(file("stdin"),F,";")
p=function(a,b)a[1]*b[1]+a[2]*b[2]
t=function(a,b,c){A=d[a,];
U=d[1,]-A
B=d[b,]-A
C=d[c,]-A
f=p(C,C)
g=p(B,C)
h=p(U,C)
i=p(B,B)
j=p(U,B)
k=f*i-g*g
u=i*h-g*j
v=f*j-g*h
min(u*k,v*k,k-u-v)>0}
any(apply(combn(2:nrow(d),3),2,function(v)t(v[1],v[2],v[3])))

Skrypt pobiera dane wejściowe ze STDIN, np Rscript script.R < inputFile.

Generuje wszystkie trójkąty z Nostatnich punktów (ostatniej linii apply(combn(...) i sprawdza, czy pierwszy punkt znajduje się w trójkącie za pomocą tfunkcji.

twykorzystuje barycentryczne sposobu decydowania, czy Ujest w ABC: (pisanie XYdla Xdo Ywektora), ponieważ (AB,AC)jest podstawą do samolotu (z wyjątkiem zdegenerowanych przypadkach, gdzie A, B, C są wyrównane), AUmogą być zapisywane jako AU = u.AB + v.ACi Ujest w MFF trójkąta u > 0 && v > 0 && u+v < 1. Zobacz na przykład tutaj, aby uzyskać bardziej szczegółowe wyjaśnienie i fajny interaktywny wykres. Uwaga: aby zapisać kilka znaków i uniknąć błędów DIV0, obliczamy tylko skrót do ui vzmodyfikowany test ( min(u*k,v*k,k-u-v)>0).

Jedyne operatory matematyczne wykorzystywane są +, -, *, min()>0.