Problem 1456. Beads on a Necklace (Convex Hulls)

We may describe a convex hull as a rubber band stretched around a list of points. Some of the points will be inside the rubber band, and some will define vertices of (or lie along the edge of) a convex polygon.

Given an n-by-2 list of points xy where each row describes a point, your job is to determine if all the points belong to the convex hull for those points. In the matrix xy, the x coordinate is the first column and the y coordinate is the second column.

So, for example, the points below form a single convex hull.

   *     *
   *     *  

In contrast, the points below do not, since the convex hull is a triangle that includes an interior point. Any polygon that includes all the points must necessarily be concave.

   *     *

Thus if

 xy = [1 1;1 2;2 2;2 1]


 allConvex(xy) => true


 xy = [1 1;3 1;2 2;2 3]
 allConvex(xy) => false

Solution Stats

55.0% Correct | 45.0% Incorrect
Last Solution submitted on Jun 22, 2020

Problem Comments

Problem Recent Solvers44

Suggested Problems

More from this Author49

Problem Tags