Problem: here_comes_santa_claus (2023 round1)

*…right down Santa Claus Lane!*

Santa Claus Lane is home to \(N\) elves, the \(i\)th of whom lives \(X_i\) meters from the start of the lane. As Santa's little helper, you're tasked to assign elves to work on toys for good little girls and boys. Specifically, you must assign each elf to work on some toy so that at least \(2\) toys get worked on, and no elf works on a toy alone.

All elves working on the same toy will meet at the point which minimizes the farthest distance that any of them would need to walk. Formally, if the elves assigned to a given toy live at \(X_1\), \(X_2\), \(…\), then they will meet at point \(P\) such that \(\max(|X_1 - P|\), \(|X_2 - P|\), \(…\)\()\) is as small as possible.

For instance, the first sample case is depicted below:

{{PHOTO_ID:838516607729325|WIDTH:700}}

Santa is supervising, and you reckon he could use some exercise. Among all valid assignments of elves to toys, what's the farthest Santa would need to walk to visit all meeting points? Santa may start and end anywhere, but will try to walk as little as possible after seeing your assignments.

# Constraints

\(1 \leq T \leq 20\)
\(4 \leq N \leq 10^5 \)
\(1 \leq X_i \leq 10^9 \)

# Input Format

Input begins with an integer \(T\), the number of test cases. Each case begins with one line containing the integer \(N\), followed by a second line containing the the \(N\) integers \(X_1 ... X_N\).

# Output Format

For the \(i\)th test case, print "`Case #i:` " followed by a single real number, the farthest distance Santa would need to walk in meters. Your answer will be considered correct if it differs from the jury's answer by at most \(10^{-6}\) meters or at most \(0.0001\)%, whichever is larger.

# Sample Explanation

In the first sample case, elves living at \(1 \,\text{m}\) and \(3 \,\text{m}\) will work on a toy. Elves living at \(7 \,\text{m}\), \(12 \,\text{m}\), and \(13 \,\text{m}\) will work on another toy, and elves at \(17 \,\text{m}\) and \(23 \,\text{m}\) will work on the third toy. The toys will be made at \(2 \,\text{m}\), \(10 \,\text{m}\) and \(20 \,\text{m}\) respectively. Santa would need to walk at least \(18 \,\text{m}\) in total to visit every meeting point.

The second sample case is depicted below. No elf is allowed to work alone and we must make two toys. One optimal way of doing this is to have the leftmost \(3\) elves work on one toy at \(2 \,\text{m}\), and the rest work on the other toy at \(4.5 \,\text{m}\). This would maximize the distance Santa would have to walk among all valid elf assignments.

{{PHOTO_ID:163905706775126|WIDTH:400}}

In the third case, the two toys will be made at \(55 \,\text{m}\) and \(5500 \,\text{m}\).



Sample input:
3
7
1 17 3 13 7 23 12
5
5 4 3 2 1
4
10 100 1000 10000


Sample output:
Case #1: 18
Case #2: 2.5
Case #3: 5445


Solution: For a given assignment, Santa will always walk from the leftmost toy to the rightmost toy. It's in our interest to get these two meeting points as far as possible. This is equivalent to independently minimizing the leftmost meeting point, while maximing the rightmost meeting point.

For all elves assigned to a toy, the meeting point will always be the average of the leftmost and rightmost elf. To minimize the leftmost meeting point, it's intuitive that grouping only the \(2\) leftmost elves will get the average as small as possible. Likewise, we group the \(2\) rightmost elves.

We can sort the elves by ascending \(x\)-coordinates \(X_1' < ... < X_N'\), find the left meeting point as \((X_2' - X_1')/2\) and the right meeting point as \((X_{N}' - X_{N-1}')/2\). The answer (i.e. the distance of Santa's walk) will be the difference between those two meeting points.

The only special case occurs if there are \(N = 5\) elves. If we did the above, we would be left with a single elf in the middle who isn't allowed to work on a toy alone. We must instead include the middle elf in one of the other two groups. When \(N \ge 6\), there are at least \(2\) middle elves in our main strategy, so they won't pose an issue.



Code: #include <algorithm>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;

double solve() {
  int N;
  cin >> N;
  vector<int> X(N);
  for (int i = 0; i < N; i++) {
    cin >> X[i];
  }
  sort(X.begin(), X.end());
  double ans = X[N-1] + X[N-2] - (X[0] + X[1]);
  if (N == 5) {
    ans = max(
      X[N-1] + X[N-3] - (X[0] + X[1]),
      X[N-1] + X[N-2] - (X[0] + X[2])
    );
  }
 return ans / 2;
}

int main() {
  int T;
  cin >> T;
  cout.precision(1);
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": " << fixed << solve() << endl;
  }
  return 0;
}