Determinar si un polígono es convexo

21

Escriba un programa para determinar si el polígono de entrada es convexo . El polígono se especifica con una línea que contiene N , el número de vértices, luego N líneas que contienen las coordenadas x e y de cada vértice. Los vértices se enumerarán en sentido horario a partir de un vértice arbitrario.

Ejemplo 1

entrada

4
0 0
0 1
1 1
1 0

salida

convex

ejemplo 2

entrada

4
0 0
2 1
1 0
2 -1

salida

concave

ejemplo 3

entrada

8
0 0
0 1
0 2
1 2
2 2
2 1
2 0
1 0

salida

convex

x y y son números enteros, n <1000 , y | x |, | y | <1,000 . Puede suponer que el polígono de entrada es simple (ninguno de los bordes se cruza, solo 2 bordes tocan cada vértice). El programa más corto gana.

Keith Randall
fuente
¿"Simple" no incluye "los bordes consecutivos no son colineales"? Además, un par de casos de prueba más: (0,0) (0,2) (2,2) (2,0) (1,1); y (1,1) (0,0) (0,2) (2,2) (2,0) - para probar los casos en los que encontrar el vértice cóncavo requiere envolver desde el final hasta el inicio.
Peter Taylor
Esta pregunta está envejeciendo, pero ... Considere agregar un ejemplo cóncavo con dos segmentos alineados, por ejemplo, una modificación del ejemplo 2: (0,0), (2,1), (4,2), (1,0) ( 2, -1). Menciono esto porque busqué el ejemplo 3 sin darme cuenta.
Jesse Millikan

Respuestas:

4

J, 105

echo>('concave';'convex'){~1=#=(o.1)([:>-.~)(o.2)|3([:-/12 o.-@-/@}.,-/@}:)\(,2&{.)j./"1}.0&".;._2(1!:1)3

Pasa las tres pruebas anteriores.

Editar: (111-> 115) Manejar puntos co-lineales eliminando ángulos de pi. Obtuve algunos personajes en otros lugares.

Editar: (115-> 105) Menos tonto.

Explicación para los discapacitados en J:

  • (1!:1)3lea STDIN a EOF. (Yo creo que.)
  • 0&".;._2 es un buen modismo para analizar este tipo de entrada.
  • j./"1}. corte la primera línea de entrada (N 0) y convierta los pares en complejos.
  • (,2&{.) agregue los dos primeros puntos al final de la lista.
  • 3(f)\ aplica f a la ventana deslizante de longitud 3 (3 puntos para un ángulo)
  • [:-/12 o.-@-/@}.,-/@}: es un verbo que transforma cada 3 puntos en un ángulo entre -pi y pi.
    • -@-/@}.,-/@}:produce (p1 - p2), (p3 - p2). (Recuerde que estos son complejos).
    • 12 o. da un ángulo para cada complejo.
    • [:-/(...) da la diferencia de los dos ángulos.
  • (o.1)([:>-.~)(o.2)| mod 2 pi, elimine los ángulos de pi (segmentos rectos) y compárelos con pi (mayor que, menor que, no importa a menos que se suponga que los puntos están enrollados en una dirección).
  • 1=#= si todos esos resultados de comparación son 1 o 0 (con autoclasificación. Esto parece tonto).
  • echo>('concave';'convex'){~ impresión convexa
Jesse Millikan
fuente
3

Python - 149 caracteres

p=[map(int,raw_input().split())for i in[0]*input()]*2
print'ccoonncvaevxe'[all((a-c)*(d-f)<=(b-d)*(c-e)for(a,b),(c,d),(e,f)in zip(p,p[1:],p[2:]))::2]
gnibbler
fuente
Creo que necesita <=, vea el ejemplo 3 que acabo de agregar.
Keith Randall el
1
dammn, esa rebanada ...
st0le
2

Ruby 1.9, 147 133 130 124 123

gets
puts ($<.map{|s|s.split.map &:to_i}*2).each_cons(3).any?{|(a,b),(c,d),(e,f)|(e-c)*(d-b)<(d-f)*(a-c)}?:concave: :convex
Lowjacker
fuente
1

scala: 297 caracteres

object C{class D(val x:Int,val y:Int)
def k(a:D,b:D,c:D)=(b.y-a.y)*(c.x-b.x)>=(c.y-b.y)*(b.x-a.x) 
def main(a:Array[String]){val s=new java.util.Scanner(System.in)
def n=s.nextInt
val d=for(x<-1 to n)yield{new D(n,n)}print((true/:(d:+d.head).sliding(3,1).toList)((b,t)=>b&&k(t(0),t(1),t(2))))}}
usuario desconocido
fuente
1
Puede afeitarse de tres caracteres utilizando en def main(a:...lugar de def main(args:....
Gareth
Sí, me di cuenta de mí mismo, pero 299 a 149 no me lleva al área de otra persona. Tal vez si encuentro otras mejoras, ah, hay una: n es un nombre de función (siguiente) y un nombre de variable.
usuario desconocido