Probability of Uncorrelated Differences in Linear Combinations

We are given two discrete random variables (X) and (Y) with a known joint distribution. We then construct (n) new random variables by forming their linear combinations [ Z_i = a_iX + b_iY, \quad \text{for } i=1,2,\dots,n, ] where (a_i) and (b_i) are given real coefficients and no two pairs ((a_i,b_i)) are identical.

Now, three distinct ones among (Z_1,Z_2,\dots,Z_n) are selected at random (i.e. one combination out of (\binom{n}{3}) is chosen uniformly). For a chosen triple ({Z_i,Z_j,Z_k}) (with (i,j,k) pairwise distinct), consider the following three propositions:

1. (p_1): (Z_i-Z_j) is uncorrelated with (Z_j-Z_k);
2. (p_2): (Z_j-Z_k) is uncorrelated with (Z_k-Z_i);
3. (p_3): (Z_k-Z_i) is uncorrelated with (Z_i-Z_j).

Recall that two random variables (U) and (V) are uncorrelated if their covariance is zero, where the covariance is defined as [ \mathrm{Cov}(U,V)=E[UV]-E[U]E[V]. ]

For example, for proposition (p_1), set [ U = Z_i-Z_j = (a_i-a_j)X+(b_i-b_j)Y, \quad V = Z_j-Z_k = (a_j-a_k)X+(b_j-b_k)Y. ] Then [ \mathrm{Cov}(U,V)= (a_i-a_j)(a_j-a_k)E[X^2] + \Bigl((a_i-a_j)(b_j-b_k)+(b_i-b_j)(a_j-a_k)\Bigr)E[XY] + (b_i-b_j)(b_j-b_k)E[Y^2]

• \bigl((a_i-a_j)\mu_X+(b_i-b_j)\mu_Y\bigr)\bigl((a_j-a_k)\mu_X+(b_j-b_k)\mu_Y\bigr), ] where (\mu_X=E[X]) and (\mu_Y=E[Y]).

Your task is to compute the probability that at least one of the three propositions (p_1,p_2,p_3) holds. The answer is given by [ \text{Probability} = \frac{\text{(number of triples for which at least one proposition is true)}}{\binom{n}{3}}. ]

Note: When checking whether a covariance is zero you may assume a tolerance of (10^{-6}) for floating-point comparisons.

inputFormat

The input consists of the following parts:

1. The first line contains an integer (M), the number of entries in the joint distribution table of (X) and (Y).

2. Each of the next (M) lines contains three numbers: (x), (y), and (p), representing a value of (X), a value of (Y), and the probability (p(x,y)) respectively. It is guaranteed that (\sum p = 1).

3. The next line contains an integer (n), the number of linear combinations (i.e. the number of (Z) variables).

4. Each of the next (n) lines contains two real numbers: (a_i) and (b_i) for (i=1,2,\dots,n). No two pairs ((a_i,b_i)) are identical.

outputFormat

Output a single line containing the probability that at least one of the three propositions holds, formatted to six decimal places.

sample

2
0 0 0.5
1 1 0.5
3
1 0
0 1
1 1

1.000000