Ближайшие точки (Время: 1 сек. Память: 16 Мб Сложность: 38%) Антон в школе начал изучать математику. Его внимание привлекло новое для него понятие числовой прямой. Антон быстро научился вычислять расстояния между двумя точками на этой прямой, задавать отрезки и интервалы на ней. Готовясь к контрольной работе, Антон столкнулся со следующей задаче…

closest_points.java

import java.util.*;
import java.io.*;

public class Main{ //имя класса должно быть Main
  public static void main(String[] argv) throws IOException{
    new Main().run();
  }
  PrintWriter pw;
  Scanner sc;

  public void run() throws IOException{
    sc = new Scanner(new File("input.txt"));
    int count = sc.nextInt();
    int[][] arr = new int[count][2];
    for (int i = 0; i < count; i++) {
      arr[i][0] = i;
      arr[i][1] = sc.nextInt();
    }
    mergeSort(arr, 0, arr.length-1);
  
    int[] pair = new int[2];
    int current, first, second;
    int last_sum = 1000000000;

    for (int i=1; i < arr.length; i++) {
      if (arr[i][1] < arr[i-1][1]){
        current = arr[i-1][1] - arr[i][1];
        first = arr[i][0];
        second = arr[i-1][0];
      } else {
        current = arr[i][1] - arr[i-1][1];
        first = arr[i-1][0];
        second = arr[i][0];
      }
      if ( pair[0] == 0 && pair[1] == 0 ){
        pair[0] = first;
        pair[1] = second;
        last_sum = current;
        continue;
      }
      if ( current < last_sum ) {
        pair[0] = first;
        pair[1] = second;
        last_sum = current;
      }
    }

    pw = new PrintWriter(new File("output.txt"));
    pw.print(last_sum + "\n");
    pair[0] += 1;
    pair[1] += 1;
    pw.print(pair[0] + " " + pair[1]);
    pw.close();
  }

  public static void qSort(int[][] a, int low, int high) {
    if (low > high)
      return;
    int x = a[(low + high) >> 1][1];
    int i = low;
    int j = high;

    while (true) {
      while (a[i][1] < x)
        ++i;
      while (x < a[j][1])
        --j;
      if (i > j)
        break;

      int[] t = a[i];
      a[i] = a[j];
      a[j] = t;
      ++i;
      --j;
      if (i > j)
        break;
    }
    qSort(a, low, j);
    qSort(a, i, high);
  }

  public static void mergeSort(int[][] a, int low, int high) {
    if (low + 1 < high) {
      int mid = (low + high) >>> 1;
      mergeSort(a, low, mid);
      mergeSort(a, mid, high);

      int size = high - low;
      int[][] b = new int[size][2];
      int i = low;
      int j = mid;
      for (int k = 0; k < size; k++) {
        if (j >= high || i < mid && a[i][1] < a[j][1]) {
          b[k] = a[i++];
        } else {
          b[k] = a[j++];
        }
      }
      System.arraycopy(b, 0, a, low, size);
    }
  }
}