Bash Number Of Disc Intersections
number_of_disc_intersections() {
local -n _a="$1"
local _c=${#_a[@]}
local -a _start _end
local _k
for ((_k = 0; _k < _c; _k++)); do _start[_k]=0; _end[_k]=0; done
for _k in "${!_a[@]}"; do
local _v=${_a[$_k]}
local _key
if (( _k < _v )); then _key=0; else _key=$(( _k - _v )); fi
(( _start[_key]++ ))
if (( _k + _v >= _c )); then _key=$(( _c - 1 )); else _key=$(( _k + _v )); fi
(( _end[_key]++ ))
done
local _sum=0 _active=0
for ((_k = 0; _k < _c; _k++)); do
_sum=$(( _sum + _active * _start[_k] + (_start[_k] * (_start[_k] - 1)) / 2 ))
_active=$(( _active + _start[_k] - _end[_k] ))
if (( _sum > 10000000 )); then
echo -1
return
fi
done
echo "$_sum"
}
This sorts disc start and end points and counts active overlaps without comparing every pair directly.