J 40 39 34 bytes
3 :'(o.1)<(>./-<./)12 o.y*+{.y'@:-
Una función diádica anónima, tomando un punto, p , como uno de sus argumentos, y una lista de puntos, P , como el otro argumento (no importa qué argumento es cuál), y regresando 0
o 1
, si p está fuera o dentro del casco convexo de P , respectivamente. El punto p , y los puntos en P , se toman como números complejos.
Ejemplo
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
o...
Python 2, función, 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)
Toma entrada, en el mismo formato que la publicación original, a través de STDIN e imprime un valor booleano que indica si p está en el casco convexo de P
Explicación
El programa prueba si la diferencia entre los ángulos máximo y mínimo (con signo) entre cualquier punto r en P , p , y un punto arbitrario fijo q en P (solo usamos el primer punto en P ), es inferior a 180 °. En otras palabras, prueba si todos los puntos en P están contenidos en un ángulo de 180 ° o menos, alrededor de p .
p está en el casco convexo de P si y solo si esta condición es falsa.
A costa de unos pocos bytes más, podemos usar un método similar que no requiere que calculemos ángulos explícitamente: tenga en cuenta que la condición anterior es equivalente a decir que p está fuera del casco convexo de P si y solo si existe una línea l a p , de modo que todos los puntos en P estén en el mismo lado de l . Si existe una línea de este tipo, también existe una línea que incide en uno (o más) de los puntos en P (podemos rotar l hasta que toque uno de los puntos en P ).
A (tentativamente) encontrar esta línea, se comienza por dejar que l sea a través de la línea P y el primer punto en P . Luego iteramos sobre el resto de los puntos en P ; si uno de los puntos está a la izquierda de l (suponemos que hay cierta direccionalidad en todo, izquierda o derecha realmente no importa), reemplazamos l con la línea que pasa por p y ese punto, y continuamos. Después de iterar sobre todo P , si (y solo si) p está fuera del casco convexo, entonces todos los puntos en P deben estar a la derecha de (o sobre) l . Verificamos que usando un segundo pase sobre los puntos en 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)
Alternativamente, para hacer lo mismo en una sola pasada, dejar a la izquierda una realidad entre dos puntos, q y r , en P , de modo que q esté a la izquierda de r si q está a la izquierda de la línea que pasa por p y r . Tenga en cuenta que a la izquierda de es una relación de orden en P si y sólo si todos los puntos de P están en el mismo lado de algunos línea que pasa por p , es decir, si p se encuentra fuera del casco convexo de P . El procedimiento descrito anteriormente encuentra el punto mínimo en PWRT este orden, es decir, el punto "más a la izquierda" en P . En lugar de realizar dos pases, podemos encontrar el máximo (es decir, el punto "más a la derecha"), así como el mínimo, puntos en P wrt en el mismo orden en un solo pase, y verificar que el mínimo esté a la izquierda del máximo, es decir, efectivamente, que a la izquierda de es transitivo.
Esto funcionaría bien si p está fuera del casco convexo de P , en cuyo caso a la izquierda de es realmente una relación de orden, pero puede romperse cuando p está dentro del casco convexo (por ejemplo, trate de averiguar qué sucedería si nos encontramos con este algoritmo, donde los puntos de P son los vértices de un pentágono regular, corriendo hacia la izquierda, y p . es su centro) Para dar cabida, alteramos ligeramente el algoritmo: seleccionamos un punto q en P , y bisect P a lo largo de la línea que pasa por p y q (es decir, dividimos P alrededor de qwrt a la izquierda de.) Ahora tenemos una "parte izquierda" y una "parte derecha" de P , cada una contenida en un medio plano, de modo que a la izquierda de es una relación de orden en cada uno; encontramos el mínimo de la parte izquierda y el máximo de la parte derecha, y los comparamos como se describió anteriormente. Por supuesto, no tenemos que dividir físicamente P , simplemente podemos clasificar cada punto en P mientras buscamos el mínimo y el máximo, en una sola pasada.
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)
sort
oround
. Creo que es más claro simplemente decir que no se permite nada hecho específicamente para la geometría. Sin embargo, ¿qué pasa con una función para agregar dos listas como vectores? ¿O una función para encontrar el argumento (ángulo) de un número complejo?