What is probability that a line joining two randomly selected coordinates from set form an angle $45°$ with one of axes?

Question

What is probability that a line joining two randomly selected coordinates from a set form an angle $45°$ with one of the axes?

For example, if we have set of coordinates $$\{(1, 2), (1, 3), (3, 3), (4, 4)\}$$ then, if my calculations is correct, the probability would be $0.125$

How I calculated this:
Number of ways to select coordinates is $4^2=16$ because even the same coordinates can be selected. To line form an angle $45°$ with one of axes, the slope of line have to be $1$ or $-1$. Out of these $16$ ways only $2$ have slope $1$ or $-1$ so probability is $\frac{2}{16} = 0.125$.

I am programming an algorithm that computes this probability but the algorithm have to check slope of every combination of coordinates so my question is:
Is there any other/faster way to compute this probability?

EDIT: I don't know if it helps, but coordinates will be only integers.

EDIT 2: Range of coordinates is from $-100000$ to $100000$. Number of coordinates will be no more than $10000$. Also probability will be computed to $6$ decimal places.

Answer 1

For any two distinct points $(x_1, y_1)$ and $(x_2, y_2)$ to form a $45^\circ$ angle with two axes, the equivalent condition is$$ x_1 + y_1 = x_2 + y_2 \ \text{or}\ x_1 - y_1 = x_2 - y_2. \tag{1} $$ Note that to compute the probability, it suffices to count the number of pairs satisfying (1) and then divide it by $\binom{n}{2}$. The algorithm below counts the number of pairs $(x_1, y_1)$ and $(x_2, y_2)$ such that$$ x_1 + y_1 = x_2 + y_2, $$ and there is an analogous algorithm that counts the number of pairs $(x_1, y_1)$ and $(x_2, y_2)$ such that$$ x_1 - y_1 = x_2 - y_2, $$

Suppose there are $n$ distinct points (x[1], y[1]), …, (x[n], y[n]).

Step1: Compute a[i] = x[i] + y[i] for $1 \leqslant i \leqslant n$. The time complexity of this step is $O(n)$.

Step 2: Sort array a. By using merge sort, the time complexity of this step is $O(n \ln n)$.

Step 3: Count the multiplicity of each a[i]. Suppose distinct values in a are $a'_1 < \cdots < a'_t$ and their respective multiplicities are $m_1, \cdots, m_t$, then compute $s = \sum\limits_{k = 0}^t \binom{m_k}{2}$.

s = 0; m = 1;
for(i = 2; i <= n; i++) {
    if(a[i] == a[i - 1]) m++;
    else {
        s += m * (m - 1) / 2;
        m = 1;
    }
}
s += m * (m - 1) / 2;

The time complexity of this step is $O(n)$.

The overall time complexity is $O(n \ln n)$.

Answer 2

Assume that you are given $N$ points $$(x_i,y_i)\in{\mathbb Z}^2\qquad(1\leq i\leq N)\ .$$ Introduce new coordinates $(u,v)$ in the plane via $$u:=x-y, \qquad v:=x+y\ .$$ You then get $N$ new coordinate pairs $(u_i,v_i)\in{\mathbb Z}^2$. Now check for coinciding $u$-, resp. $v$-coordinates of these points, and take care of the resulting multiplicities. E.g., if you find $4$ points with $u_i=5$ you have to count these coincidences with weight ${4\choose2}=6$ towards the probability you are interested in.