21
\$\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.

\$\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\$ 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\$ Apr 21, 2011 at 19:38

4 Answers 4

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.
\$\endgroup\$
3
\$\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]
\$\endgroup\$
2
  • \$\begingroup\$ I think you need <=, see example 3 I just added. \$\endgroup\$ Apr 19, 2011 at 14:33
  • 1
    \$\begingroup\$ dammn, that slice... \$\endgroup\$
    – st0le
    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
\$\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))))}}
\$\endgroup\$
2
  • 1
    \$\begingroup\$ You can shave of three chars by using def main(a:... instead of def main(args:.... \$\endgroup\$
    – Gareth
    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\$ Apr 22, 2011 at 10:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.