Фон

Выпуклая оболочка конечного числа точек является наименьшим выпуклым многоугольником , который содержит все точки, либо в качестве вершин или на внутренней. Для получения дополнительной информации см. Этот вопрос о PGM, который очень хорошо его определяет .

вход

N+1N >= 3Через 2-D координаты ( ) STDIN(с другими обычными входами для гольфа тоже разрешены) в следующем формате (количество десятичных знаков может варьироваться, но можно предположить, что оно остается «разумным», и каждое число может быть представлено как число с плавающей точкой):

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

Вывод

Истинное значение, напечатанное в STDOUT(или эквивалентное), если первая точка в списке ( (0.00;0.00000)в примере выше) находится в выпуклой оболочке других N точек, и ложное значение в противном случае.

Это код-гольф , поэтому выигрывает самое короткое решение в байтах.

• Граничные случаи : вы можете вернуть любое значение (но не потерпите крах), если точка лежит на границе выпуклой оболочки (т. Е. На стороне или на вершине на внешней границе корпуса), так как это нулевая вероятность событие (при любой разумной вероятности).

• Запрещено : все (язык, оператор, структура данных, встроенный или пакет), которое существует только для решения геометрических задач (например, ConvexHull Mathematica ). Допускаются математические инструменты общего назначения (векторы, матрицы, комплексные числа и т. Д.).

тесты

• Должен вернуться TRUE: spiralTest1-TRUE , squareTest1-TRUE
• Должен вернуться FALSE: spiralTest2-FALSE , squareTest2-FALSE

J, 40 39 34 байта

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

Анонимная двоичная функция, принимающая точку p в качестве одного из своих аргументов и список точек P в качестве другого аргумента (не имеет значения, какой аргумент является каким), и возвращающая 0или 1, если p находится вне или внутри выпуклой оболочки Р , соответственно. Точка p и точки в P принимаются за комплексные числа.

пример

  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

или...

Python 2, функция, 121 103, полная программа, 162

Python 3, 149 байт

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)

Принимает ввод в том же формате, что и исходное сообщение, через STDIN и печатает логическое значение, указывающее, находится ли p в выпуклой оболочке P

объяснение

Программа проверяет, составляет ли разница между максимальным и минимальным (знаковыми) углами между любой точкой r в P , p и фиксированной произвольной точкой q в P (мы просто используем первую точку в P ) менее 180 °. Другими словами, он проверяет, содержатся ли все точки в P под углом 180 ° или меньше вокруг p . p находится в выпуклой оболочке P тогда и только тогда, когда это условие ложно.

Ценой еще нескольких байтов мы можем использовать аналогичный метод, который не требует от нас явного вычисления углов: обратите внимание, что вышеприведенное условие эквивалентно утверждению, что p находится вне выпуклой оболочки P, если и только если он существует прямая от l до p , так что все точки в P находятся на одной стороне от l . Если такая линия существует, то есть также такая линия, которая инцидентна одной (или более) из точек в P (мы можем вращать l, пока она не коснется одной из точек в P ).

Для того, чтобы (предварительно) найти эту линию, мы начнем, позволяя л быть прямой , проходящей через р и первая точка P . Затем мы перебираем остальные точки в P ; если одна из точек находится слева от l (мы предполагаем, что некоторая направленность повсеместно, влево или вправо не имеет значения), мы заменяем l на линию, проходящую через p и эту точку, и продолжаем. После того, как мы итерировали по всей P , если (и только если) p находится вне выпуклой оболочки, то все точки в P должны быть справа от (или на) l . Мы проверяем это, используя второй проход по точкам в P,

Python 2, 172 байта

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)

В качестве альтернативы, чтобы сделать то же самое за один проход, пусть слева-от- другого будет реальность между любыми двумя точками q и r в P , так что q слева от r, если q слева линии, проходящей через р и р . Обратите внимание , что к-влево от является отношение порядка P тогда и только тогда , когда все точки Р находятся на одной и той же стороны некоторой линии , проходящей через р , то есть, если р находится вне выпуклой оболочки P . Процедура, описанная выше, находит минимальную точку в PWRT этот порядок, то есть «крайний левый» точку P . Вместо того, чтобы выполнить два прохода, мы можем найти максимум (т. Е. «Самую правую» точку), а также минимум, точки в P по одному и тому же порядку за один проход, и убедиться, что минимум находится слева от максимум, т. е. фактически то, что слева от является переходным.

Это будет хорошо работать, если p находится за пределами выпуклой оболочки P , и тогда слева направо на самом деле является отношение порядка, но оно может нарушиться, когда p находится внутри выпуклой оболочки (например, попытайтесь выяснить, что будет произойдет, если мы запустим этот алгоритм, где точки в P - это вершины правильного пятиугольника, бегущего против часовой стрелки, а p - его центр.) Чтобы приспособиться, мы немного изменим алгоритм: мы выбираем точку q в P и делим пополам P вдоль линии, проходящей через p и q (т.е. мы разбиваем P вокруг qпо левому краю.) Теперь у нас есть «левая часть» и «правая часть» P , каждая из которых содержится в полуплоскости, так что слева направо есть отношение порядка на каждой; мы находим минимум левой части и максимум правой части и сравниваем их, как описано выше. Конечно, нам не нужно физически делить пополам P , мы можем просто классифицировать каждую точку в P, поскольку мы ищем минимум и максимум, за один проход.

Python 2, 194 байта

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)

Октава, 82 72 байта

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

Идея состоит в том, чтобы проверить, имеет ли решение линейная программа min {c'x: Ax = b, e'x = 1, x> = 0}, где e - вектор всех единиц, столбцы A - координаты облако точек, а b - контрольная точка, а c - произвольная. Другими словами, мы пытаемся представить b как выпуклую комбинацию столбцов A.

Чтобы запустить скрипт, используйте octave -f script.m <input.dat

R 207 байт

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

Сценарий берет свои входные данные из STDIN, например Rscript script.R < inputFile.

Он генерирует все треугольники из Nпоследних точек (последней линии apply(combn(...) и проверяет, находится ли первая точка в треугольнике, используя tфункцию.

tиспользует метод области, чтобы решить, если Uнаходится в ABC: (запись (ABC)для области ABC) Uв ABCiff (ABC) == (ABU) + (ACU) + (BCU). Кроме того, площади рассчитываются по формуле детерминанта (см. Здесь хорошую демонстрацию от Wolfram).

Я подозреваю, что это решение более подвержено ошибкам, чем мои другие, но оно работает на моих тестовых примерах.

R, 282 байта

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

Сценарий берет свои входные данные из STDIN, например Rscript script.R < inputFile.

Он генерирует все треугольники из Nпоследних точек (последней линии apply(combn(...) и проверяет, находится ли первая точка в треугольнике, используя tфункцию.

tиспользует барицентрический метод, чтобы решить, Uнаходится ли в ABC: (запись XYдля вектора Xto Y), поскольку (AB,AC)является базисом для плоскости (за исключением вырожденных случаев, когда A, B, C выровнены), AUможет быть записан как AU = u.AB + v.ACи Uнаходится в треугольнике, если u > 0 && v > 0 && u+v < 1, Смотрите, например, здесь для более подробного объяснения и хороший интерактивный график. NB: чтобы сэкономить несколько символов и ошибок избежать div0, мы только вычислить ярлык uи vи модифицированный тест ( min(u*k,v*k,k-u-v)>0).

Единственный математические операторы используются +, -, *, min()>0.