Biorąc pod uwagę uporządkowaną listę 2 lub więcej dwuwymiarowych punktów kartezjańskich, wyprowadzaj prawdziwą wartość, jeśli ścieżka dotyka siebie lub przecina się; w przeciwnym razie wypisz wartość fałszowania, jeśli się nie dotyka ani nie przecina.

Możesz założyć, że kolejne punkty na liście są różne.

Przykłady:

(0,0), (1,0) -> falsey
(0,0), (1,0), (0,0) -> truthy
(0,0), (1,0), (1,1), (0,0) -> truthy
(0,0), (2,0), (1,1), (1,-1) -> truthy
(0,0), (10,0), (0,1), (10,1), (0,2), (10,2) -> falsey

Zwróć uwagę, że wszystkie podane tutaj współrzędne są liczbami całkowitymi. Możesz wspierać wprowadzanie współrzędnych dowolnych wartości z {liczba całkowita, dziesiętna, wymierna, zmiennoprzecinkowa, ...}. Ale twoje obliczenia implementacyjne muszą dać poprawne odpowiedzi na wszelkie podane dane wejściowe.

Python 2 , 315 309 298 382 380 372 bajtów

s=sorted
w=lambda(x,y),(X,Y),(z,w):(X-x)*(w-y)-(z-x)*(Y-y)
def I(a,b):p,q=s(a);P,Q=s(b);n,N,m,M=w(p,q,P),w(p,q,Q),w(P,Q,p),w(P,Q,q);return(q>=P)*(Q>=p)if{n,N,m,M}=={0}else(b[1]!=a[0])*(n*N<=0>=m*M)
def f(l):
 i=0
 while i<len(l)-2:
	x=l[i:i+3];i+=1
	if w(*x)==0and s(x)==x:l.pop(i);i-=1
 L=zip(l,l[1:]);return any(I(*l)for l in[(k,x)for i,k in enumerate(L)for x in L[:i]])

Wypróbuj online!

Używa algorytmu stąd , w połączeniu z tą odpowiedzią SO dla segmentów współliniowych.

Edycja: Naprawiono dla odcinków linii kontynuujących w tym samym kierunku (np. (0,0),(1,0),(2,0)) Poprzez usunięcie punktu środkowego (w wyniku (0,0),(2,0)).

Eukleides , 154 148 bajtów

number i (set p)
g=card(p);h=g;n=0;e=p[0];q=e.e
for d in p
if h<g-1 
q=q.e
n=card(intersection(d.e,q))>1or d on q?1|n
end
e=d;h=h-1
end;return n;end

Funkcja o nazwie, iże przekazała zestaw punktów, zwraca 0 lub 1. Średniki i podziały linii są wymienne do zakończenia polecenia, po prostu zrzuciłem kilka rzeczy ze względu na utrzymanie krótkiego kodu, ponieważ nie jesteśmy przyzwyczajeni do czytelności i tak kod tutaj.

Eukleides to język geometrii płaskiej przede wszystkim do grafiki, ale także z przyzwoitymi zdolnościami programistycznymi. Pomyślałem, że będzie świetnie do tego zadania, ale kilka rzeczy mnie frustrowało. Po pierwsze, warto zauważyć, że zestawy w Eukleidach są w zasadzie tablicami punktów, a gdy ma to zastosowanie, są renderowane jako ścieżki wykonane z połączonych segmentów linii. Eukleides obsługuje iteracyjne generowanie zestawów za pomocą loci, podobnie jak pętla for, która tworzy zestaw w procesie. Gdybym był w stanie użyć locus, wygoliłby bajty, ale najwyraźniej Eukleides nie lubi odwoływać się do częściowo uformowanego locus od siebie.

Inną poważną frustracją było to, że jeśli pozornie dwa identyczne segmenty linii znajdują się jeden nad drugim, intersectionzwraca tylko jeden punkt obrażenia (co, jak sądzę, ma sens, byłyby nieskończone przecięcia). Moja metoda polega zasadniczo na zbudowaniu ścieżki o krok do tyłu i przetestowaniu następnego segmentu linii pod kątem przecięć ze ścieżką. Z powodu wyżej wspomnianego zachowania na skrzyżowaniu osobno sprawdzam, czy punkt znajduje się na ścieżce.

Edycja : Odetnij 1 bajt, zmieniając kolejność orinstrukcji, aby umożliwić wcześniejsze usunięcie spacji or; 5 dodatkowych bajtów, zmieniając ten ifblok w operację potrójną.

Przypadki testowe:

ta=point(0,0).point(1,0)
tb=point(0,0).point(1,0).point(0,0)
tc=point(0,0).point(1,0).point(1,1).point(0,0)
td=point(0,0).point(2,0).point(1,1).point(1,-1)
te=point(0,0).point(10,0).point(0,1).point(10,1).point(0,2).point(10,2)
print i(ta);print i(tb);print i(tc);print i(td);print i(te)

0
1
1
1
0