Suppose you are maintaining the convex hull of a set of points P that grows over time. That is, if a point gets added to P you must immediately compute the convex hull of the new set of points. However, rather than doing it in O(|P| log |Pl) time each time P is updated, your goal is to update the convex hull after each point is added in time that is linear in the size of the current convex hull. The convex hull you maintain must be a list of points H forming the convex hull of P and the points in H are listed in counterclockwise order around the hull. Throughout, you may assume that no 3 points in P are collinear, that no two points in P are identical, and that |P> 3 is always true. For both parts below, you should provide an argument justifying the correctness of the algorithm and the running time analysis. A. Suppose you already know the points H forming the convex hull of a set of points P. Given a point p & P, show how to determine if p lies within the convex hull or not in O(H) time. By within the convex hull, we mean that if we drew the line segments connecting consecutive points of H to form the convex hull (including a segment between the last point in H and the first one), then p is within the convex hull if it is in the inside of the resulting convex polygon. B. Now suppose, again, that you already know the convex hull H of P. Suppose a new point p is to be added to P and that it does not lie within the convex hull of P. Show how to update H in O(H) time to so it becomes the convex hull of PU {p}. Suppose you are maintaining the convex hull of a set of points P that grows over time. That is, if a point gets added to P you must immediately compute the convex hull of the new set of points. However, rather than doing it in O(|P| log |Pl) time each time P is updated, your goal is to update the convex hull after each point is added in time that is linear in the size of the current convex hull. The convex hull you maintain must be a list of points H forming the convex hull of P and the points in H are listed in counterclockwise order around the hull. Throughout, you may assume that no 3 points in P are collinear, that no two points in P are identical, and that |P> 3 is always true. For both parts below, you should provide an argument justifying the correctness of the algorithm and the running time analysis. A. Suppose you already know the points H forming the convex hull of a set of points P. Given a point p & P, show how to determine if p lies within the convex hull or not in O(H) time. By within the convex hull, we mean that if we drew the line segments connecting consecutive points of H to form the convex hull (including a segment between the last point in H and the first one), then p is within the convex hull if it is in the inside of the resulting convex polygon. B. Now suppose, again, that you already know the convex hull H of P. Suppose a new point p is to be added to P and that it does not lie within the convex hull of P. Show how to update H in O(H) time to so it becomes the convex hull of PU {p}