Problem: watering_well_ch2 (2022 round1)

**Note: The only difference between this chapter and [chapter 1](https://www.facebook.com/codingcompetitions/hacker-cup/2022/round-1/problems/B1) is that here, coordinates may be up to \(\mathbf{10^9}\).**

Boss Rob just planted \(N\) happy little trees in his yard, which can be represented on a Cartesian plane. The \(i\)th tree is located at coordinates \(t_i = (A_i, B_i)\). Now, he's looking for the best spot to build a well in order to provide water to them. He considers the *inconvenience* of a potential well location \(p\) to be the sum of the squared Euclidean distances to every tree:

\[\sum_{i=1}^{N} \Vert \,p - t_i \Vert ^ 2 \]

Rob wants to pick a location for his well, well... well. Help him determine the inconvenience for \(Q\) different potential well locations, \((X_1, Y_1), ..., (X_Q, Y_Q)\). To reduce output size, please print the sum of inconveniences for all potential well locations, modulo \(1{,}000{,}000{,}007\).


# Constraints

\(1 \le T \le 50\)
\(1 \le N, Q \le 500{,}000\)
\(0 \le A_i, B_i, X_i, Y_i \le \mathbf{10^9}\)
All \((A_i, B_i)\) are distinct within a given test case.
All \((X_i, Y_i)\) are distinct within a given test case.

The total sum of \(N\) and \(Q\) across all test cases is at most \(3{,}000{,}000\).


# Input Format

Input begins with a single integer \(T\), the number of test cases. For each case, there is first a line containing a single integer \(N\). Then, \(N\) lines follow, the \(i\)th of which contains two space-separated integers \(A_i\) and \(B_i\). Then there is a line containing a single integer \(Q\). Then, \(Q\) lines follow, the \(i\)th of which contains two space-separated integers \(X_i\) and \(Y_i\).


# Output Format

For the \(i\)th test case, print a line containing `"Case #i: "`, followed by a single integer, the sum of inconveniences for all \(Q\) well locations, modulo \(1{,}000{,}000{,}007\).


# Sample Explanation

The first two sample cases are depicted below:

{{PHOTO_ID:3620154144878669|WIDTH:700}}

In the first case, the total inconvenience is \(18 + 34 = 52\):

- For the well at \((2, 5)\), the inconvenience is the sum of the squared Euclidean distance to both trees, which is \(3^2 + 3^2 = 18\).
- For the well at \((6, 6)\), the inconvenience is \(32 + 2 = 34\).

In the second case, the total inconvenience is \(47 + 31 + 53 = 131\):

- For the well at \((3, 1)\), the inconvenience is \(4 + 5 + 13 + 25 = 47\).
- For the well at \((5, 2)\), the inconvenience is \(17 + 2 + 2 + 10 = 31\).
- For the well at \((6, 5)\), the inconvenience is \(41 + 8 + 4 + 0 = 53\).


Sample input:
4
2
2 2
5 5
2
2 5
6 6
4
1 1
4 3
6 3
6 5
3
3 1
5 2
6 5
8
2837 745
62 1162
2634 1112
1746 2618
847 127
986 1993
732 1273
2003 1998
4
1276 2231
1234 1234
287 2371
3000 3000
5
283746263 475619273
987361523 361738847
281936352 666152443
143042069 482716253
1000000000 100000000
5
0 0
123456789 987654321
192837465 918273645
135792468 864209753
703692581 185296307


Sample output:
Case #1: 52
Case #2: 131
Case #3: 110090622
Case #4: 391473143


Solution: With coordinates values up to \(10^9\), we can no longer loop through each axis as in chapter 1. We can still take advantage of the fact that the \(x\) and \(y\) components of the answer can be found independently. Let's see what happens when we expand the formula for the \(x\)-component of the squared distance:

\[ \begin{aligned} \sum_{i=1}^{N} (p_x - A_i)^2 &= \sum_{i=1}^{N} [\,p_x^2 - 2 p_x A_i + A_i^2] \\ &= \sum_{i=1}^{N} p_x^2 - \sum_{i=1}^{N} 2 p_x A_i + \sum_{i=1}^{N} A_i^2 \\ &= N p_x^2 - 2 p_x \sum_{i=1}^{N} A_i + \sum_{i=1}^{N} A_i^2 \end{aligned} \]

The sums in the middle and last terms do not actually depend on the query, so they can both be precomputed as constants. The rest is just arithmetic, done in \(\mathcal{O}(1)\) per query.

Special care must be taken with the modular arithmetic of these computations. Overflows of 64-bit integers can happen easily if more than two terms are multiplied without modding. Also since subtraction is involved, the remainder operator \(\%\) in many languages may yield negative results where the number theoretic modulo would be positive. One possible way to implement modular subtraction using the \(\%\) operator is \((a - b) \text{ mod } M = ((a\;\%\;M) - (b\;\%\;M) + M) \;\%\;M\).

[See David Harmeyer's solution video here.](https://www.youtube.com/watch?v=bUa3fyd2Fus)


Code: #include <iostream>
using namespace std;

using LL = long long;
const int LIM = 500000;
const int MOD = 1000000007;

inline LL add(LL a, LL b) {
  return ((a % MOD) + (b % MOD)) % MOD;
}

inline LL sub(LL a, LL b) {
  return (((a - b) % MOD) + MOD) % MOD;
}

inline LL mul(LL a, LL b) {
  return (a % MOD)*(b % MOD) % MOD;
}

int solve() {
  int N, Q;
  LL A, B, X, Y;
  LL sumA = 0, sumAsq = 0;
  LL sumB = 0, sumBsq = 0;
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> A >> B;
    sumA = (sumA + A) % MOD;
    sumB = (sumB + B) % MOD;
    sumAsq = (sumAsq + (A*A % MOD)) % MOD;
    sumBsq = (sumBsq + (B*B % MOD)) % MOD;
  }
  cin >> Q;
  LL ans = 0;
  for (int i = 0; i < Q; i++) {
    cin >> X >> Y;
    // sum_{j} ((X - A_j)^2) = sum(X^2) - 2*X*sum(A_j) + sum(A_j^2)
    ans = add(ans, add(sub(mul(mul(X, X), N), mul(2LL*X, sumA)), sumAsq));
    ans = add(ans, add(sub(mul(mul(Y, Y), N), mul(2LL*Y, sumB)), sumBsq));
  }
  return ans;
}

int main() {
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": " << solve() << endl;
  }
  return 0;
}