Computer Science

Computational Geometry

Convex Hull


The following text file contains a set, PP, of one thousand 2d Cartesian points.

Your task is to compute the convex hulls of PP. Let VV be the set of vertices of the convex hulls of the point PP. How many elements does VV contain?

Suppose we are given three coordinate points a=(x0,y0)a=(x_0,y_0), b=(x1,y1)b=(x_1,y_1) and c=(x2,y2)c=(x_2,y_2). Your task is to devise a routine that tests whether point cc lies to the right of the directed line which goes from point aa to point bb. If so, the angle formed by sweeping from aa to cc in a counterclokwise manner around bb is acute.

Each line of the following text file contains the three points arranged like the following:


How many of the triples satisfy the test described above?


Problem Loading...

Note Loading...

Set Loading...