20
\$\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\$
  • \$\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\$ – Peter Taylor Apr 19 '11 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\$ – Jesse Millikan Apr 21 '11 at 19:38
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\$
  • \$\begingroup\$ I think you need <=, see example 3 I just added. \$\endgroup\$ – Keith Randall Apr 19 '11 at 14:33
  • 1
    \$\begingroup\$ dammn, that slice... \$\endgroup\$ – st0le Apr 20 '11 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\$
  • 1
    \$\begingroup\$ You can shave of three chars by using def main(a:... instead of def main(args:.... \$\endgroup\$ – Gareth Apr 22 '11 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\$ – user unknown Apr 22 '11 at 10:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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