Problem: watering_well_ch1 (2022 round1)

**Note: The only difference between this chapter and [chapter 2](https://www.facebook.com/codingcompetitions/hacker-cup/2022/round-1/problems/B2) is that here, coordinates are only up to \(\mathbf{3{,}000}\).**

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 55\)
\(1 \le N, Q \le 500{,}000\)
\(0 \le A_i, B_i, X_i, Y_i \le \mathbf{3{,}000}\)
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:3159344294326237|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:
3
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


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


Solution: The key insight is that the squared distance \(||p - t||^2 = (p_x - t_x)^2 + (p_y - t_y)^2\) between a well at point \(p\) and tree at point \(t\) can be obtained by treating each of the two axes independently.

We can project the \(x\)-coordinates of trees \(t_1, \ldots, t_N\) onto a number line (the \(x\)-axis), and likewise for the \(y\)-coordinates onto the \(y\)-axis. There may multiple trees with a given \(x\) or \(y\), so we can precompute their frequencies in arrays \(\text{xcnt}[x]\) and \(\text{ycnt}[y]\). The time and space complexities will both be linear on the largest possible values of \(x\) and \(y\), which are only up to \(3{,}000\).

Then, we see that the inconvenience of a well at point \(p\) can be computed as:

\[\begin{aligned} \sum_{i=1}^{N} \lVert p - t_i \rVert^2 &= \sum_{i=1}^{N} [(p_x - A_i)^2 + (p_y - B_i)^2] \\ &= \sum_{i=1}^{N} (p_x - A_i)^2 + \sum_{i=1}^{N} (p_y - B_i)^2 \\ &= \sum_{x=0}^{3{,}000} \text{xcnt}[x]\cdot(p_x - x)^2 + \sum_{y=0}^{3{,}000} \text{ycnt}[y]\cdot (p_y - y)^2 \end{aligned}\]

Computing this directly will take \(\mathcal{O}(3{,}000)\) steps on each of the \(Q = 500{,}000\) queries, for a total of ~\(1.5\) billion steps. This should already be fast enough to pass within the \(6\) minute time limit. However, we can optimize further by precomputing the answer for all \(3{,}000^2\) possible coordinates, after which, each query can be answered in \(\mathcal{O}(1)\).

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


Code: #include <iostream>
using namespace std;

const int LIM = 500000;
const int LIM2 = 3005;
const int MOD = 1000000007;

int N, Q;
int A[LIM], B[LIM];

int solve() {
  int cntX[LIM2] = {0}, cntY[LIM2] = {0};
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> A[i] >> B[i];
    cntX[A[i]]++;
    cntY[B[i]]++;
  }
  cin >> Q;
  long long X, Y, ans = 0;
  for (int i = 0; i < Q; i++) {
    cin >> X >> Y;
    for (int x = 0; x < LIM2; x++) {
      ans = (ans + ((long long)cntX[x]*(X - x) % MOD)*(X - x)) % MOD;
    }
    for (int y = 0; y < LIM2; y++) {
      ans = (ans + ((long long)cntY[y]*(Y - y) % MOD)*(Y - y)) % MOD;
    }
  }
  return ans;
}

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