CROWNS - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

MEDIUM

EXPLANATION

Try all ordered pairs of points p,q as the first and last points in the crown (the endpoints of the “base” of the crown). Translate the points so p is at the origin and then rotate so q is on the positive x axis. Now, discard all points with non-positive y coordinate, x coordinates at most 0 or at least the x coordinate of q (after rotating, of course). Finally, among these points keep only the one with minimum y coordinate among all points that share the same x coordinate. Sort these remaining points by their x coordinate.

For each point r (including the endpoints p,q), let U[r] be the maximum area of a crown that involves point r where the point after r is above r and let D[r] be the maximum area of a crown that involves point r where the point after r is below r. The largest area of a crown involving base points p,q is then U[p]. The base case is D[q] = infeasible and U[q] = 0, the idea being that the point before q in a crown must decrease to q. From an arbitrary point r, we compute D[r] by trying all points s whose x coordinate is greater than r and such that there is no other point lying below the line formed by the line r-s. The value of D[r] is the maximum of U[s] + (s.x-r.x) * (r.y+s.y)/2 over all such points s. U[r] is computed similarly. We can calculate D[r] in linear time given that the coordinates are sorted according to x coordinate by keeping track of the least slope of a line between r and a point seen so far in our sweep. Then we can determine, in constant time, whether a given point s has a point under the line r-s or not. In fact, it’s not too hard to see that both U[r] and D[r] can be computed in a single sweep. The running time is O(n^4) since there are O(n^2) pairs of points to try, O(n) values D[r] and U[r] to compute, and computing each such value takes O(n) time.

One final note is that there is always a solution given that no three points are collinear. To see this, note that we can triangulate the set of points. Any triangle is a feasible crown by selecting the longest side to be a base.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.