fundo

O casco convexo de um número finito de pontos é o menor polígono convexo que contém todos os pontos, como vértices ou no interior. Para mais informações, consulte esta pergunta no PGM, que a define muito bem .

Entrada

N+1As coordenadas 2D ( N >= 3) passaram STDIN(com outras entradas de golfe comuns também permitidas) no seguinte formato (o número de casas decimais pode variar, mas você pode assumir que permanece "razoável" e que cada número pode ser representado como um ponto flutuante):

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

Resultado

Um valor verdadeiro impresso para STDOUT(ou equivalente) se o primeiro ponto da lista ( (0.00;0.00000)no exemplo acima) estiver no casco convexo dos outros N pontos e, caso contrário, um valor falso.

Isso é código-golfe , então a solução mais curta em bytes vence.

• Casos de borda : você pode retornar qualquer valor (mas não trava) se o ponto estiver na borda do casco convexo (ou seja, de um lado ou de um vértice na fronteira externa do casco), pois é uma probabilidade zero evento (sob qualquer probabilidade razoável).

• Proibido : qualquer coisa (idioma, operador, estrutura de dados, embutido ou pacote) que existe apenas para resolver problemas geométricos (por exemplo, o ConvexHull do Mathematica ). Ferramentas matemáticas de uso geral (vetores, matrizes, números complexos etc.) são permitidas.

Testes

• Deve retornar TRUE: spiralTest1-TRUE , squareTest1-TRUE
• Deve retornar FALSE: spiralTest2-FALSE , squareTest2-FALSE

J, 40. 39. 34 bytes

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

Função diádica anônima, tendo um ponto p como um de seus argumentos e uma lista de pontos P como o outro argumento (não importa qual argumento é qual) e retornando 0ou 1, se p estiver fora ou dentro do casco convexo de P , respectivamente. O ponto p e os pontos em P são tomados como números complexos.

Exemplo

  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

ou...

Python 2, função, 121 103programa completo 162

Python 3, 149 bytes

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)

Recebe a entrada, no mesmo formato da postagem original, por meio de STDIN e imprime um valor booleano indicando se p está no casco convexo de P

Explicação

O programa testa se a diferença entre os ângulos máximo e mínimo (assinado) entre qualquer ponto r em P , p e um ponto arbitrário fixo q em P (usamos apenas o primeiro ponto em P ) é menor que 180 °. Em outras palavras, ele testa se todos os pontos em P estão contidos em um ângulo de 180 ° ou menos, em torno de p . p está no casco convexo de P se e somente se essa condição for falsa.

À custa de mais alguns bytes, podemos usar um método semelhante que não exige o cálculo explícito de ângulos: Observe que a condição acima é equivalente a dizer que p está fora do casco convexo de P, se e somente se houver uma linha l a p , de modo que todos os pontos em P estejam do mesmo lado de l . Se essa linha existir, também haverá uma linha que é incidente em um (ou mais) dos pontos em P (podemos girar l até que toque em um dos pontos em P ).

Para (provisoriamente) encontrar essa linha, começamos deixando l ser a linha através p eo primeiro ponto em P . Nós então iteramos sobre o restante dos pontos em P ; se um dos pontos estiver à esquerda de l (assumimos que alguma direcionalidade em toda a parte, esquerda ou direita não importa realmente), substituímos l pela linha que passa por pe nesse ponto e continuamos. Depois de iterarmos sobre todo P , se (e somente se) p estiver fora do casco convexo, todos os pontos em P deverão estar à direita de (ou sobre) l . Verificamos que, usando uma segunda passagem sobre os pontos em P.

Python 2, 172 bytes

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)

Como alternativa, para fazer a mesma coisa em uma única passagem, deixe uma esquerda para a esquerda entre dois pontos, q e r , em P , de modo que q esteja à esquerda de r se q estiver à esquerda da linha que passa por p e r . Note-se que a-a-esquerda do é uma relação de ordem em P se e só se todos os pontos em P estão no mesmo lado da linha que passa através alguns p , isto é, se P está fora do casco convexo de P . O procedimento descrito acima encontra o ponto mínimo em Pwrt este fim, isto é, o ponto "mais à esquerda" em P . Em vez de executar duas passagens, podemos encontrar os pontos máximo (ou seja, o ponto "mais à direita"), bem como o mínimo, em P, escrever a mesma ordem em uma única passagem e verificar se o mínimo está à esquerda da máximo, isto é, efetivamente, que a esquerda é transitiva.

Isso funcionaria bem se p estivesse fora do casco convexo de P ; nesse caso, o lado esquerdo é realmente uma relação de ordem, mas pode quebrar quando p estiver dentro do casco convexo (por exemplo, tente descobrir o que será acontece se executamos esse algoritmo em que os pontos em P são os vértices de um pentágono regular, rodando no sentido anti-horário ep é seu centro.) Para acomodar, alteramos ligeiramente o algoritmo: Selecionamos um ponto q em P e dividimos P ao longo da linha que passa através de p e q (ou seja, nós partição P torno qAgora, temos uma "parte esquerda" e uma "parte direita" de P , cada uma contida em um semiplano, de modo que a esquerda é uma relação de ordem em cada uma; encontramos o mínimo da parte esquerda e o máximo da parte direita e os comparamos como descrito acima. Obviamente, não precisamos dividir fisicamente P , podemos simplesmente classificar cada ponto em P enquanto procuramos o mínimo e o máximo, em uma única passagem.

Python 2, 194 bytes

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)

Oitava, 82 72 bytes

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

A idéia é verificar se o programa linear min {c'x: Ax = b, e'x = 1, x> = 0} tem uma solução, onde e é um vetor de todos, colunas de A são as coordenadas de a nuvem de pontos eb é o ponto de teste ec é arbitrário. Em outras palavras, tentamos representar b como uma combinação convexa de colunas de A.

Para executar o script, use octave -f script.m <input.dat

R, 207 bytes

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

O script recebe suas entradas do STDIN, por exemplo Rscript script.R < inputFile.

Ele gera todos os triângulos a partir dos Núltimos pontos (a última linha apply(combn(...) e verifica se o primeiro ponto está no triângulo usando a tfunção

tusa o método area para decidir se Uestá em ABC: (escrevendo (ABC)para a área de ABC) Uestá em ABCiff (ABC) == (ABU) + (ACU) + (BCU). Além disso, as áreas são calculadas usando a fórmula determinante (veja aqui uma boa demonstração da Wolfram).

Suspeito que esta solução seja mais propensa a erros numéricos do que a minha outra, mas funciona nos meus casos de teste.

R, 282 bytes

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

O script recebe suas entradas do STDIN, por exemplo Rscript script.R < inputFile.

Ele gera todos os triângulos a partir dos Núltimos pontos (a última linha apply(combn(...) e verifica se o primeiro ponto está no triângulo usando a tfunção

tusa o método barentocêntrico para decidir se Uestá em ABC: (escrevendo XYpara o vetor Xto Y), pois (AB,AC)é uma base para o plano (exceto para os casos degenerados em que A, B, C estão alinhados), AUpode ser escrito como AU = u.AB + v.ACe Uestá no triângulo se u > 0 && v > 0 && u+v < 1. Veja, por exemplo, aqui uma explicação mais detalhada e um bom gráfico interativo. NB: para economizar alguns caracteres e erros a evitar DIV0, só calcular um atalho para ue ve um teste modificado ( min(u*k,v*k,k-u-v)>0).

Os únicos operadores matemáticos utilizados são +, -, *, min()>0.