Triangle partitioning

This was a problem in the 2010 Pacific ACM-ICPC contest. The gist of it is trying to find a way to partition a set of points inside a triangle into three subtriangles such that each partition contains exactly a third of the points.

Input:

• Coordinates of a bounding triangle: (v1x,v1y),(v2x,v2y),(v3x,v3y)


• A number 3n < 30000 representing the number of points lying inside the triangle


• Coordinates of the 3n points: (x_i,y_i) for i=1...3n

Output:

• A point (sx,sy) that splits the triangle into 3 subtriangles such that each subtriangle contains exactly n points.

The way the splitting point splits the bounding triangle into subtriangles is as follows: Draw a line from the splitting point to each of the three vertices. This will divide the triangle into 3 subtriangles.

We are guaranteed that such a point exists. Any such point will suffice (the answer is not necessarily unique).

Here is an example of the problem for n=2 (6 points). We are given the coordinates of each of the colored points and the coordinates of each vertex of the large triangle. The splitting point is circled in gray.

Can someone suggest an algorithm faster than O(n^2)?

---