Part I: Given a convex polygon G and a query point q, output the two (left and right) supporting lines through q if q is not inside the polygon. A line is a supporting line of G if the line passes through at least one point of G and all other points lie on one side of the line. A directed supporting line from q to v, where v is a vertex of G, is a left supporting line, if all the points of G lie to the right of the directed line, and is a right supporting line, if all the points of G lie to the left of it.

Part II: Given a convex polygon G and a query line L, determine if the line L intersects G. If it does, reply with a 'YES' message and find the points of G that it intersects. Else reply with a 'NO' message.

This assignment is designed for you to implement the bimodal search method. Notice that you need not explicitly compute all the function values, f(0), f(1),…, f(n-1) for vertices v0, v1, …, vn-1 of G. Instead you compute the function values, as needed. Your program should be written in C/C++ using object classes available in the library or new objects developed on your own. Documentation of your code is necessary. In addition to the running code, you must include the pseudo-code, and give the timing analysis of your algorithm. Note that the brute force algorithm is not allowed.