22
\$\begingroup\$

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.

Improve this question
\$\endgroup\$
2
  • \$\begingroup\$ "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. \$\endgroup\$ Commented Apr 19, 2011 at 16:22
  • \$\begingroup\$ 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. \$\endgroup\$ Commented Apr 21, 2011 at 19:38

4 Answers 4

Reset to default
4
\$\begingroup\$

J, 105

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

Passes all three tests above.

Edit: (111->115) Handle co-linear points by eliminating angles of pi. Gained a few characters elsewhere.

Edit: (115->105) Less dumb.

Explanation for the J-impaired:

  • (1!:1)3 read STDIN to EOF. (I think.)
  • 0&".;._2 is a nice idiom for parsing this kind of input.
  • j./"1}. lop off first line of input (N 0) and convert pairs to complexes.
  • (,2&{.) tack first two points onto the end of the list.
  • 3(f)\ applies f to sliding window of length 3 (3 points for an angle)
  • [:-/12 o.-@-/@}.,-/@}: is a verb that transforms each 3 points into an angle between -pi and pi.
    • -@-/@}.,-/@}: produces (p1 - p2),(p3 - p2). (Recall that these are complexes.)
    • 12 o. gives an angle for each complex.
    • [:-/(...) gives the difference of the two angles.
  • (o.1)([:>-.~)(o.2)| mod 2 pi, eliminate angles of pi (straight segments), and compare to pi (greater than, less than, doesn't matter unless the points are supposed to be wound in one direction).
  • 1=#= if all those comparison result 1 or 0 (With self-classify. This seems dumb.)
  • echo>('concave';'convex'){~ print convex.
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

Python - 149 chars

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]
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ I think you need <=, see example 3 I just added. \$\endgroup\$ Commented Apr 19, 2011 at 14:33
  • 1
    \$\begingroup\$ dammn, that slice... \$\endgroup\$ Commented Apr 20, 2011 at 6:39
2
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
1
\$\begingroup\$

scala: 297 chars

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))))}}
Improve this answer
\$\endgroup\$
2
  • 1
    \$\begingroup\$ You can shave of three chars by using def main(a:... instead of def main(args:.... \$\endgroup\$ Commented Apr 22, 2011 at 8:40
  • \$\begingroup\$ Yes, I noticed myself, but 299 to 149 doesn't bring me in the area of someone else. Maybe if I find other improvements - ah, there is one: n is a function name (next) and a variable name. \$\endgroup\$ Commented Apr 22, 2011 at 10:13

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.