VK Cup 2018 - Уайлд-кард Раунд 1 |
---|
Закончено |
На прямой находится n точек, причем i-я точка имеет координату xi. Координаты всех точек различны.
Определите число m — минимальное количество точек, которые нужно добавить на прямую так, чтобы расстояния между каждой парой соседних точек на прямой были одинаковыми.
В первой строке следует целое число n (3 ≤ n ≤ 100 000) — количество точек.
Во второй строке следует последовательность целых чисел x1, x2, ..., xn ( - 109 ≤ xi ≤ 109) — координаты точек. Координаты всех точек различны. Точки могут следовать в любом порядке.
Выведите число m — минимальное количество точек, которые нужно добавить на прямую так, чтобы расстояния между каждой парой соседних точек на прямой были одинаковыми.
3
-5 10 5
1
6
100 200 400 300 600 500
0
4
10 9 0 -1
8
В первом примере достаточно добавить одну точку с координатой 0.
Во втором примере расстояния между всеми парами начальных точек равны между собой, поэтому ничего добавлять не нужно.
Название |
---|