Optimal City Shortcut

You are given N cities located at distinct positions in the plane. The cities are numbered from 1 to N and the coordinates of city i are given by \( (x_i, y_i) \).

There is an existing road between each adjacent pair of cities \(i\) and \(i+1\) (for \(i=1,2,\dots,N-1\)). The length of the road \(R_i\) connecting city \(i\) and city \(i+1\) is the Manhattan distance \[ |x_i-x_{i+1}|+|y_i-y_{i+1}|. \]

The diameter of this network is defined as the maximum over the lengths of the shortest paths between any pair of cities. In the chain structure described above the diameter is equal to the distance (along the chain) between city 1 and city \(N\).

You are allowed to add one new road connecting any two different cities \(a\) and \(b\) (\(a < b\)). The length of the new road is defined as \[ |x_a-x_b|+|y_a-y_b|. \]

After adding the new road the distance between any two cities is the minimum over all valid paths that may use the new road. In particular, for any two cities \(i\) and \(j\) the shortest distance is \[ \min\Big\{D_{chain}(i,j),\; d(i,a)+|x_a-x_b|+|y_a-y_b|+d(b,j),\; d(i,b)+|x_a-x_b|+|y_a-y_b|+d(a,j)\Big\}, \] where \(d(i,j)\) is the Manhattan chain distance along the original road sequence.

Your task is to choose a pair of cities \(a\) and \(b\) to connect such that the new diameter of the network is minimized, and to output that minimum possible diameter.

Insight: Let the cities be indexed from 1 to \(N\) and let a prefix sum array \(P\) be defined by \(P[1]=0\) and for \(i\ge2\), \(P[i]=P[i-1]+(|x_{i-1}-x_i|+|y_{i-1}-y_i|)\). Note that the original diameter is \(P[N]\). When a new road is added between city \(a\) and city \(b\) (with \(1\le a < b\le N\)), there are three potential candidates that determine the new diameter:

• The maximum distance within the left segment: \(P[a]\) (i.e. from city 1 to city \(a\)).
• The maximum distance within the right segment: \(P[N]-P[b]\) (i.e. from city \(b\) to city \(N\)).
• The maximum distance between any two cities on the cycle formed by the new road; a good estimate for this is the ceiling of \(\frac{(P[b]-P[a])+\text{shortcut}}{2}\) where the shortcut length is \(|x_a-x_b|+|y_a-y_b|\).

Also note that the path from city 1 to city \(N\) which uses the new road has length \(P[a]+(|x_a-x_b|+|y_a-y_b|)+ (P[N]-P[b])\), which is always no more than the original diameter \(P[N]\) (since the Manhattan distance satisfies the triangle inequality and is usually a strict improvement).

The new diameter when edge \((a,b)\) is added can then be computed as the maximum of the three values below:

[ \max\Big{ P[a],; P[N]-P[b],; \left\lceil\frac{(P[b]-P[a])+\big(|x_a-x_b|+|y_a-y_b|\big)}{2}\right\rceil,; P[a]+\big(|x_a-x_b|+|y_a-y_b|\big)+(P[N]-P[b]) \Big}. ]

Your goal is to try all valid choices of \(a\) and \(b\) and report the minimum possible new diameter.

Function Signature:

long long shortcut(int N, long long X[], long long Y[]);

No input/output operations should be performed in your submitted code.

inputFormat

This function will be tested by calling shortcut with the following parameters:

• int N: the number of cities.
• long long X[] and long long Y[]: arrays of length N where X[i] and Y[i] are the coordinates of city i+1.

outputFormat

The function should return a long long integer, the minimum possible diameter of the city network after adding one new road optimally.

sample

4
0 2 3 3
0 0 0 3

6