Computer Science

# Convex Hull

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

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

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

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

[x0,y0,x1,y1,x2,y2]

How many of the triples satisfy the test described above?

×