Waste less time on Facebook — follow Brilliant.
Back to all chapters

Computational Geometry

Computers are being used more and more to solve geometric problems, like modeling physical objects such as brains and bridges.

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:


How many of the triples satisfy the test described above?


Problem Loading...

Note Loading...

Set Loading...