(Аналіз Ніка Ву)

Наш перший інстинкт, коли ми намагаємося визначити, який пункт пропустити, - спробувати їх усі. Якщо ми вирішимо пропустити кожну точку та обчислити нову відстань напряму, то для обчислення відстані знадобиться приблизно N операцій, і буде приблизно N точок для перевірки, що дає нам алгоритм, який виконується приблизно за N операцій. Це буде занадто повільно, коли N становитиме 100 000.

Давайте детальніше розглянемо, що відбувається, коли ви пропускаєте певний пункт. Якщо ми пронумеруємо точки від 1 до N і пропустимо точку K, то шлях, яким ми йдемо, пролягає від точки 1 до точки K-1 , потім від точки K-1 до точки K+1 , а потім від точки K+1 до точки N . Відстань цього шляху точно дорівнює наступному:

• (загальна відстань без пропуску будь-якої точки) - (відстань між точками K-1 і K ) - (відстань між точками K і K+1 )+(відстань між точками K-1 і K+1 ).

Якщо ми обчислюємо загальну відстань, не пропускаючи жодної точки заздалегідь, тоді визначення довжини шляху, коли ми хочемо пропустити певну точку, більше не вимагає N операцій! Це вимагає лише постійної кількості операцій, і це буде достатньо швидко.

import java.io.*;
import java.util.*;
public class marathon {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new FileReader("marathon.in"));
    PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("marathon.out")));
    int n = Integer.parseInt(br.readLine());
    int[] x = new int[n];
    int[] y = new int[n];
    for(int i = 0; i < n; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      x[i] = Integer.parseInt(st.nextToken());
      y[i] = Integer.parseInt(st.nextToken());
    }
    int totalDistance = 0;
    for(int i = 1; i < n; i++) {
      totalDistance += Math.abs(x[i] - x[i-1]) + Math.abs(y[i] - y[i-1]);
    }
    int largestSkip = 0;
    for(int i = 1; i < n-1; i++) {
      int noSkipDistance = Math.abs(x[i+1] - x[i]) + Math.abs(x[i] - x[i-1]) + Math.abs(y[i+1] - y[i]) + Math.abs(y[i] - y[i-1]);
      int skipDistance = Math.abs(x[i+1] - x[i-1]) + Math.abs(y[i+1] - y[i-1]);
      largestSkip = Math.max(largestSkip, noSkipDistance - skipDistance);
    }
    pw.println(totalDistance - largestSkip);
    pw.close();
  }
}