Given an array A of N integers we draw N discs in a 2D plane, such that i-th disc has center in (0,i) and a radius A[i]. We say that k-th disc and j-th disc intersect, if and k-th and j-th discs have at least one common point.

Write a function

int number_of_disc_intersections(int[] A);

which given an array A describing N discs as explained above, returns the number of pairs of intersecting discs. For example, given N=6 and

there are 11 pairs of intersecting discs:

so the function should return 11.

The function should return -1 if the number of intersecting pairs exceeds 10,000,000. The function may assume that N does not exceed 10,000,000.

#include <stdio.h>
#include <vector>

int number_of_disc_intersections ( const std::vector<int> &A ) {
   // write your code here
    size_t n = A.size();
    if(n==0) return -1;
    

    long long num=0;
    for(size_t i=0; i<n; i++)
    {
        for(size_t j=i+1; j<n; j++)
        {
            if( j-i<= A[i]+A[j] /*&& j -i + A[i] >= A[j] && j-i + A[j] >= A[i] */)
            {
                //printf("%d %d\n", i, j);
                num++;
                if(num>=10000000)
                    return -1;
            }
        }
    }

    return num;
}

int main()
{
    int a[]={1,5,2,1,4,0};
    std::vector<int> A(a, a+sizeof(a)/sizeof(a[0]));
    int i=number_of_disc_intersections(A);
    printf("%d\n",i);
}

http://stackoverflow.com/questions/4801242/algorithm-to-calculate-number-of-intersecting-discs

http://www.devcomments.com/q490073/Algorithm-to-calculate-number-intersecting-discs