Garden Fence - ICPC Latin America 2011

The problem statement for Garden Fence is available here.

This currently is the problem with the second lowest number of total users who got it accepted and the one with least submissions of all among those from ICPC Latin America 2011 available at the Live Archive.

One important thing to notice before we start trying to place the fence is that we can make its line get as close to a tree (point) as we can without really crossing it, so there is no need to worry about cutting trees which get in the fence's way.

Now, the problem asks us to draw a line to separate the points into two disjoint sets in such a way to minimize a given sum. So, testing every line created by each pair of distinct points should give us the answer, there are N^2 such lines and for each of them we need to see to which side each point belongs, this takes O(N) with the naïve approach, what gives an overall complexity of O(N^3), which is too slow for this problem.

Still thinking about the naïve approach, what could be improved to reduce its complexity? Calculating the whole sum for each pair is making it become too slow, could that be changed so that the current sum could be used to calculate the sum for the next pair of points? Yes, that is possible and is exactly what I did to solve this problem. I just needed a good ordering for the points.

So the idea for my solution is:

For each point:

• Sort other points according to their angles with current point
• Calculate for the first point in the ordered set the sum of each side of the line comprised by it and the current point
• For each point in the ordered set:
• Rotate the line, in such a way that the current point of the ordered set changes sides
• Update the sums and check to see if there is a new minimum 

Special care must be taken with collinear points which line cross the current point, they must all be processed at once. Four different sums exist that need to be kept track of, the sums on each side of the line of each kind of point, the composition of them gives the final answer.

The complexity of sorting the points is O(NlgN) and the complexity of rotating the line is O(N) for each point, as this is done once for each point, that gives us O(N^2 + N^2lgN) = O(N^2lgN), and this is fast enough for this problem.

My code is available at codepad