Schreiben Sie ein Programm, um festzustellen, ob das Eingabepolygon konvex ist . Das Polygon wird mit einer Linie angegeben, die N enthält , die Anzahl der Scheitelpunkte, und dann mit N Linien, die die x- und y- Koordinaten jedes Scheitelpunkts enthalten. Die Scheitelpunkte werden ab einem beliebigen Scheitelpunkt im Uhrzeigersinn aufgelistet.

Beispiel 1

Eingang

4
0 0
0 1
1 1
1 0

Ausgabe

convex

Beispiel 2

Eingang

4
0 0
2 1
1 0
2 -1

Ausgabe

concave

Beispiel 3

Eingang

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

Ausgabe

convex

x und y sind ganze Zahlen, N <1000 und | x |, | y | <1000 . Sie können davon ausgehen, dass das Eingabepolygon einfach ist (keine der Kanten kreuzt sich, nur 2 Kanten berühren jeden Scheitelpunkt). Kürzeste Sendung gewinnt.

J, 105

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

Besteht alle drei oben genannten Tests.

Bearbeiten: (111-> 115) Behandeln Sie kolineare Punkte, indem Sie die Pi-Winkel eliminieren. Ich habe ein paar Charaktere woanders bekommen.

Bearbeiten: (115-> 105) Weniger dumm.

Erklärung für die J-beeinträchtigten:

• (1!:1)3Lesen Sie STDIN zu EOF. (Ich glaube.)
• 0&".;._2 ist eine nette Redewendung für das Parsen dieser Art von Eingaben.
• j./"1}. Hüpfe aus der ersten Eingabezeile (N 0) und wandle Paare in Komplexe um.
• (,2&{.) Heften Sie die ersten beiden Punkte an das Ende der Liste.
• 3(f)\ gilt f für Schiebefenster der Länge 3 (3 Punkte für einen Winkel)
• [:-/12 o.-@-/@}.,-/@}: ist ein Verb, das jeweils 3 Punkte in einen Winkel zwischen -pi und pi umwandelt.
  • -@-/@}.,-/@}:erzeugt (p1 - p2), (p3 - p2). (Denken Sie daran, dass dies Komplexe sind.)
  • 12 o. gibt einen Winkel für jeden Komplex an.
  • [:-/(...) gibt die Differenz der beiden Winkel an.
• (o.1)([:>-.~)(o.2)| mod 2 pi, eliminiere die Winkel von pi (gerade Segmente) und vergleiche mit pi (größer als, kleiner als, spielt keine Rolle, wenn die Punkte nicht in eine Richtung gewickelt werden sollen).
• 1=#= Wenn alle diese Vergleiche zu 1 oder 0 führen (Mit Selbsteinstufung. Dies scheint dumm.)
• echo>('concave';'convex'){~ Drucken Sie konvex.

Python - 149 Zeichen

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]

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

Scala: 297 Zeichen

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