1. We saw in class a formula for determining whether a given set of
   three points is in clockwise order, counterclockwise order, or
   colinear, by computing the value of a quadratic polynomial of the
   input coordinates and testing whether it is positive, negative, or
   zero respectively. Describe how to use this primitive to solve the
   following problem: given two line segments in the plane, test whether
   they cross or do not cross. You may assume that no three endpoints of
   the line segments lie on the same line as each other.

2. [de Berg et al., ex. 1.6b] Let P be a non-convex polygon, with no
   self-crossings. Describe an algorithm that computes the convex hull
   of P in O(n) time. [Hint: Use a variant of Graham scan where the
   vertices are not sorted by their coordinates but are in some other
   order.]

3. [de Berg et al., ex. 1.7abd] Consider the following alternative
   approach to computing the convex hull of a set of points in the
   plane: We start with the rightmost point. This is the first point p1
   of the convex hull. Now imagine that we start with a vertical line
   and rotate it clockwise until it hits another point p2. This is the
   second point on the convex hull. We continue rotating the line but
   this time around p2 until we hit a point p3. In this way we continue
   until we reach p1 again.

    a. Give pseudocode for this algorithm.

    b. What degenerate cases (special position inputs) can occur and how
    can we deal with them?

    c. Prove that the algorithm can be implemented to run in time O(n*h)
    where h is the complexity of the convex hull.