21
1
Write a program to determine if the input polygon is convex. The polygon is specified with one line containing N, the number of vertices, then N lines containing the x and y coordinates of each vertex. The vertices will be listed clockwise starting from an arbitrary vertex.
example 1
input
4
0 0
0 1
1 1
1 0
output
convex
example 2
input
4
0 0
2 1
1 0
2 -1
output
concave
example 3
input
8
0 0
0 1
0 2
1 2
2 2
2 1
2 0
1 0
output
convex
x and y are integers, N<1000, and |x|,|y|<1000. You may assume that the input polygon is simple (none of the edges cross, only 2 edges touch each vertex). Shortest program wins.
"Simple" doesn't include "consecutive edges are non-collinear"?!
Also, a couple more test-cases: (0,0) (0,2) (2,2) (2,0) (1,1); and (1,1) (0,0) (0,2) (2,2) (2,0) - to test the cases where finding the concave vertex requires wrapping from the end back to the start. – Peter Taylor – 2011-04-19T16:22:34.120
This question is aging, but... Consider adding a concave example with two aligned segments, e.g. a modification of example 2: (0,0),(2,1),(4,2),(1,0)(2,-1). I bring this up because I fudged around example 3 without realizing it. – Jesse Millikan – 2011-04-21T19:38:43.953