PROBLEM LINK:
Author: Devendra Agarwal
Tester: Kevin Atienza
Editorialist: Kevin Atienza
PREREQUISITES:
Convex hull
PROBLEM:
Given A_1, \ldots, A_N, a tree is planted at point (A_i,A_j) for every pair i < j. What is twice the area enclosed by the minimum-perimeter fence surrounding the trees?
QUICK EXPLANATION:
For each 1 \le j \le N, let m(j) := \min _ {i< j} A _ i and M(j) := \max _ {i< j} A _ i. These values can be computed in linear time by maintaining the running minimum and maximum.
The answer is twice the area of the convex hull of the following set of (at most) 2N points:
Twice the area of a lattice point polygon is always an integer, and this value can be computed using the shoelace formula:
EXPLANATION:
Convex hull
It doesn’t take too long to discover that this “minimum perimeter fence” is just the convex hull of the given points. (If you’re not convinced of this, see this link for an explanation, which also works in our case.) So we just want to compute the area of the convex hull of some N(N-1)/2 points. The problem is that this is a lot of points. Even just looping through all these points will exceed the time limit.
However, we can actually ignore most of them. For every three collinear points A, B and C in that order, B can essentially be ignored. This is because a convex set by definition is a set containing all line segments between each pair of its points. Since the convex hull is convex, this means it contains the segment AC, which contains B automatically. Thus, we can ignore B altogether.
This means that we only need to keep at most two points in each horizontal line, the leftmost and rightmost. So for a fixed j > 1, we don’t have to include all points (A_i,A_j) for all 1 \le i < j. We only need to include \left(\min_{i< j} A_i,A_j\right) and \left(\max_{i< j} A_i,A_j\right). This leaves us with at most 2N points, so any standard fast convex hull algorithm can now compute the convex hull of all points!
Area of a polygon
Finally, we need to compute twice the area of this polygon. Since the vertices are on lattice points, by Pick’s theorem, twice the area is guaranteed to be an integer. But how do we compute it? We can use the area formula: For a polygon with M vertices (x_0,y_0),(x_1,y_1),\ldots (x_M,y_M) with (x_0,y_0) = (x_M,y_M), the area is the following:
(This is called the shoelace formula)
To get twice the area, simply ignore the \frac{1}{2}. This formula can be computed trivially in O(M) time!
To get a sense of why this formula works, first ignore the absolute value signs. The resulting value,
is known as the signed area of the polygon. The absolute value is the actual area, while the sign determines which direction we traversed the polygon: a counterclockwise traversal gives a positive sign, and a clockwise traversal gives a negative sign.
The value \left(x_{i-1}y_i - y_{i-1}x_i\right) is the “cross product” of the vectors \langle x_{i-1}, y_{i-1}\rangle and \langle x_i,y_i\rangle, which we can interpret as the signed area of the parallelogram with vertices (0,0), (x_{i-1},y_{i-1}), (x_{i-1}+x_i,y_{i-1}+y_i) and (x_i,y_i). Thus, half of that value, \frac{1}{2} \left(x_{i-1}y_i - y_{i-1}x_i\right), is the signed area of the triangle with vertices (x_{i-1},y_{i-1}), (x_i,y_i), and the origin.
Under this interpretation, we can now interpret the signed area formula as the sum of signed areas of triangles along a counterclockwise traversal of the polygon. As we wrap around the polygon, these triangles with positive and negative area will overlap, but the parts outside the polygon will cancel out and sum to 0, leaving only the area inside the reference triangle. This works even if the origin is inside or outside the polygon. I recommend trying it out on paper!
Time Complexity:
O(N \log N)
