Optimal Polygon Perimeter
Contest: Lyft Level 5 Challenge 2018 - Final Round
Difficulty rating: 2100
Tags: dp, geometry

You are given $$$n$$$ points on the plane. The polygon formed from all the $$$n$$$ points is strictly convex, that is, the polygon is convex, and there are no three collinear points (i.e. lying in the same straight line). The points are numbered from $$$1$$$ to $$$n$$$, in clockwise order.

We define the distance between two points $$$p_1 = (x_1, y_1)$$$ and $$$p_2 = (x_2, y_2)$$$ as their Manhattan distance: $$$$$$d(p_1, p_2) = |x_1 - x_2| + |y_1 - y_2|.$$$$$$

Furthermore, we define the perimeter of a polygon, as the sum of Manhattan distances between all adjacent pairs of points on it; if the points on the polygon are ordered as $$$p_1, p_2, \ldots, p_k$$$ $$$(k \geq 3)$$$, then the perimeter of the polygon is $$$d(p_1, p_2) + d(p_2, p_3) + \ldots + d(p_k, p_1)$$$.

For some parameter $$$k$$$, let's consider all the polygons that can be formed from the given set of points, having any $$$k$$$ vertices, such that the polygon is not self-intersecting. For each such polygon, let's consider its perimeter. Over all such perimeters, we define $$$f(k)$$$ to be the maximal perimeter.

Please note, when checking whether a polygon is self-intersecting, that the edges of a polygon are still drawn as straight lines. For instance, in the following pictures:

In the middle polygon, the order of points ($$$p_1, p_3, p_2, p_4$$$) is not valid, since it is a self-intersecting polygon. The right polygon (whose edges resemble the Manhattan distance) has the same order and is not self-intersecting, but we consider edges as straight lines. The correct way to draw this polygon is ($$$p_1, p_2, p_3, p_4$$$), which is the left polygon.

Your task is to compute $$$f(3), f(4), \ldots, f(n)$$$. In other words, find the maximum possible perimeter for each possible number of points (i.e. $$$3$$$ to $$$n$$$).

Input format:
The first line contains a single integer $$$n$$$ ($$$3 \leq n \leq 3\cdot 10^5$$$) — the number of points.

Each of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^8 \leq x_i, y_i \leq 10^8$$$) — the coordinates of point $$$p_i$$$.

The set of points is guaranteed to be convex, all points are distinct, the points are ordered in clockwise order, and there will be no three collinear points.

Output format:
For each $$$i$$$ ($$$3\leq i\leq n$$$), output $$$f(i)$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, for $$$f(3)$$$, we consider four possible polygons:

- ($$$p_1, p_2, p_3$$$), with perimeter $$$12$$$.
- ($$$p_1, p_2, p_4$$$), with perimeter $$$8$$$.
- ($$$p_1, p_3, p_4$$$), with perimeter $$$12$$$.
- ($$$p_2, p_3, p_4$$$), with perimeter $$$12$$$.

For $$$f(4)$$$, there is only one option, taking all the given points. Its perimeter $$$14$$$.

In the second example, there is only one possible polygon. Its perimeter is $$$8$$$.

Example input:
4
2 4
4 3
3 0
1 3

Example output:
12 14

Example input:
3
0 0
0 2
2 0

Example output:
8

Editorial:
I will show 2 solutions, both of which work in $$$\mathcal{O}(n)$$$ time. First, it is not hard to notice that we can only consider polygons that are convex.
Observation: For a convex polygon, the given definition of "polygon perimeter" is equivalent to the perimeter of the bounding rectangle (aligned with the axis), of our polygon. If we look at some convex polygon, and 4 values $$$max_x, min_x, max_y, min_y$$$ representing the maximal $$$x$$$ coordinate of a point, minimal $$$x$$$, maximal and minimal $$$y$$$, then the perimeter of the bounding rectangle is simply $$$2 * (max_x - min_x + max_y - min_y)$$$.
This simple rephrase gives us a bonus, and crucial observation: It is enough for us to take 4 points from the input, such that the perimeter of their polygon is the maximal possible (and is equal to the perimeter of the polygon formed from $$$n$$$ points). We will consider these the extreme points. Note that after taking the extreme points, it does not matter which other points we take. So, this solves all $$$f(4), \ldots, f(n)$$$.
We are left with $$$f(3)$$$ to compute (maximal triangle perimeter). Following are 2 solutions to do it:
Solution 1: Let's show that the optimal triangle uses at least 2 of the extreme points. Imagine some optimal triangle, and its bounding rectangle. Notice that since each edge of the bounding rectangle must touch some vertex of the triangle (it is bounding after all), and we have 4 edges and 3 vertices, then there must be some vertex of the triangle that touches 2 edges of the rectangle (so it coincides with a rectangle vertex). If this is the case, we know that in comparison with the 2 other vertices, this vertex has "extremal" X and Y coordinates (minimal/maximal X, and minimal/maximal Y). Without loss of generality, assume this vertex has maximum X and Y. Then to optimize the perimeter, the other two vertices should have smallest possible X and smallest possible Y. We can pick these 2 vertices to be 2 of the extreme points (one with minimal X and one with minimal Y). So, this shows we just need to iterate over every adjacent pair of extreme vertices, and over all other points as the last vertex. This takes $$$\mathcal{O}(n)$$$.
Solution 2: This solution is more general, and is an extension of the problem to find the 2 most distant points (manhattan distance). The triangle perimeter is an expression with 6 terms: $$$|x_1 - x_2| + |y_1 - y_2| + \ldots + |y_3 - y_1|$$$. We wish the maximize this expression, but the absolute value is troubling us. For each term, there are 2 cases: either it is positive, so the absolute value does nothing, or it is negative, so the absolute value negates it. In total, for the 6 terms we have $$$2^6 = 64$$$ options to place signs between them. We will call such option a setting.
For any setting, the advantage now is that we can accumulate terms: For example the setting $$$++---+$$$, evaluates the expression to:
We solve every setting by its own, and over all settings we take the maximal answer.
Please note, that this strategy only works to find the maximal value of the expression, not minimal. The proof of this is left as an exercise to the reader :) (I promise it is not difficult).
Given 6 constants $$$c_1, c_2, ..., c_6$$$, we want to find 3 indicies $$$i < j < k$$$ to maximize: $$$c_1 * x_i + c_2 * y_i + ... + c_6 * y_k$$$. We define 3 arrays:
• $$$P_i = c_1 \cdot x_i + c_2 \cdot y_i$$$
• $$$Q_i = c_3 \cdot x_i + c_4 \cdot y_i$$$
• $$$R_i = c_5 \cdot x_i + c_6 \cdot y_i$$$
So this whole solution is $$$\mathcal{O}(n)$$$, with a constant of 64. In general, to compute $$$f(k)$$$ this solution takes $$$\mathcal{O}(n \cdot 4^k \cdot k)$$$ time, without any observations.