Учитывая упорядоченный список из 2 или более двумерных декартовых точек, выведите истинное значение, если путь касается самого себя или самопересекается; в противном случае выведите ложное значение, если оно не касается самого себя или не пересекается.

Вы можете предположить, что последовательные пункты в списке различны.

Примеры:

(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

Обратите внимание, что все координаты, которые я дал здесь, являются целыми числами. Вы можете поддерживать координированные входные данные, которые вам нравятся, из {целых, десятичных, рациональных, с плавающей точкой, ...}. Но ваши расчеты реализаций должны давать правильные ответы на любые входные данные.

Python 2 , 315 309 298 382 380 372 байта

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

Попробуйте онлайн!

Использует алгоритм из здесь , в сочетании с этим SO ответ на коллинеарных сегментов.

Редактировать: Исправлено для отрезков, продолжающихся в том же направлении (например (0,0),(1,0),(2,0)) путем удаления средней точки (в результате (0,0),(2,0)).

Евклейд , 154 148 байт

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

Функция с таким именем i, передала набор точек, возвращает 0 или 1. Точки с запятой и разрывы строк взаимозаменяемы для завершения команды, я просто смешал несколько вещей вместе, чтобы сделать код визуально коротким, так как мы не привыкли к разборчивости в любом случае код здесь.

Eukleides - это язык плоской геометрии, предназначенный главным образом для графического вывода, но также с приличными возможностями программирования. Я думал, что это было бы здорово для этой задачи, но некоторые вещи расстроили меня. Во-первых, стоит отметить, что множества в Евклиде являются по существу массивами точек и, когда это применимо, отображаются в виде путей, состоящих из соединенных отрезков. Eukleides поддерживает итеративную генерацию наборов с помощью локусов, похожих на цикл for, который создает набор в процессе. Если бы я мог использовать локус, он бы сбрил байты, но, видимо, Евклейд не любит ссылаться на частично сформированный локус изнутри себя.

Другое серьезное разочарование заключалось в том, что если, по-видимому, два одинаковых отрезка находятся друг над другом, intersectionвозвращает только одну оскорбительную точку (что, я думаю, имеет смысл, если бы пересечения были бесконечными). Мой метод заключается в том, чтобы построить путь на один шаг позади и проверить следующий отрезок линии на наличие пересечений с путем. Из-за вышеупомянутого поведения пересечения я проверяю отдельно, находится ли точка на пути.

Редактировать : обрезать 1 байт, переупорядочив orоператор, чтобы учесть удаление пробела раньше or; Еще 5 байтов, превратив этот ifблок в троичную операцию.

Тестовые случаи:

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