Учитывая массив A
из N
целых чисел, мы рисуем диски N
в 2D-плоскости, так что i-й диск имеет центр в (0,i)
и радиус A[i]
. Мы говорим, что k-й диск и j-й диск пересекаются, если k-й и j-й диски имеют хотя бы одну общую точку.
Напишите функцию
int number_of_disc_intersections(int[] A);
который задал массив A
, описывающий диски N
, как описано выше, возвращает число пар пересекающихся дисков. Например, с учетом N=6
и
A[0] = 1
A[1] = 5
A[2] = 2
A[3] = 1
A[4] = 4
A[5] = 0
имеется 11 пар пересекающихся дисков:
0th and 1st
0th and 2nd
0th and 4th
1st and 2nd
1st and 3rd
1st and 4th
1st and 5th
2nd and 3rd
2nd and 4th
3rd and 4th
4th and 5th
поэтому функция должна возвращать 11.
Функция должна возвращать -1, если число пересекающихся пар превышает 10 000 000. Функция может предполагать, что N
не превышает 10 000 000.