Points

Created by LXC on Wed Jun 14 13:11:47 2023

https://codeforces.com/problemset/problem/76/E

ranting: 1700

tag: implementation, math

problem

给出二维平面上的n个整数坐标点。

求所有两个坐标的直线距离的平方之和。

$1\le n \le 10^5$

solution

暴力做法是枚举任意两个点求其距离的平方，然后累加到答案中。$O(n^2)$时间复杂度会超时。

现在考虑优化到$O(n^2)$.

对于两个点$(x1,y1)$和$(x2,y2)$的距离的平方计算公式为$(x2-x1)^2 + (y2-y1)^2$，也就是说我们可以分别计算x和y的贡献。

举个例子来说，如果给出的坐标为$(x1,y1),(x2,y2),(x3,y3)$

答案应当是$(x2-x1)^2 + (y2-y1)^2 + (x3-x1)^2 + (y3-y1)^2 + (x3-x2)^2 + (y3-y2)^2$

可以拆分为$(x2-x1)^2 + (x3-x1)^2 + (x3-x2)^2$和$(y2-y1)^2 + (y3-y1)^2 + (y3-y2)^2$

可以给x以及y坐标排序再寻找相邻前缀是否存在子问题的关系。

设给出的n个坐标的x值排序后为$x_1, x_2, \cdot, x_n$；设给出的n个坐标的y值排序后为$y_1, y_2, \cdot, y_n$。

定义状态$R_i$为$x_1,x_2,\cdots,x_{i+1}$中任意两个点之间的距离平方和。

为方便计算$R_i$和$R_{i-1}$的递推关系，设dx是排序后相邻两个坐标的距离，$dx_i = x_{i+1}-x_{i}$。

我们观察一个例子$dx_1 = a, dx_2 = b, dx_3 = c, dx_4 = d$

$R_1 = a^2$

$R_2 = R_1+(a+b)^2+b^2 = R_1+2b^2+2ab+a^2$

$R_3 = R_2+(a+b+c)^2+(b+c)^2+c^2 = R_2+3c^2+2(a+2b)c+R_2-R_1$

$R_4 = R_3+(a+b+c+d)^2+(b+c+d)^2+(c+d)^2+d^2=R_3+4d^2+2(a+2b+3c)d+R_3-R_2$

通过观察得到递推式$R_i = 2R_{i-1}-R_{i-2}+i\cdot dx_i^2+2r_idx_i$，其中$R_0 = 0, R_1 = dx_1^2$。$r_i = \sum \limits_{j=1}^ij\cdot dx_{j}$。

对于n个点的y值同理可以定义状态$C_i$为$y_1,y_2,\cdots,y_{i+1}$中任意两个点之间的距离平方和。$dy_i = y_{i+1}-y_{i},c_i = \sum \limits_{j=1}^ij\cdot dy_{j}$。得到递推式$C_i = 2C_{i-1}-C_{i-2}+i\cdot dy_i^2+2c_idy_i$，其中$C_0 = 0, C_1 = dy_1^2$。

至此$R_{n-1}+C_{n-1}$为所求。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 100005
#define MOD 998244353
using namespace std;

ll x[N], y[N];
ll dx[N], dy[N];
ll r[N], c[N];
ll R[N], C[N];

void sol() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
    }
    sort(x + 1, x + n + 1);
    sort(y + 1, y + n + 1);
    for (int i = 1; i < n; i++) {
        dx[i] = x[i + 1] - x[i];
        dy[i] = y[i + 1] - y[i];
        // cout << i << " " << dx[i] << " " << dy[i] << "\n";
    }

    for (int i = 1; i < n; i++) {
        r[i] += r[i - 1] + i * dx[i];
        c[i] += c[i - 1] + i * dy[i];
        // cout << i << " " << r[i] << " " << c[i] << "\n";
    }
    R[1] = dx[1] * dx[1];
    C[1] = dy[1] * dy[1];
    for (int i = 2; i < n; i++) {
        R[i] =
            2 * R[i - 1] - R[i - 2] + i * dx[i] * dx[i] + 2 * r[i - 1] * dx[i];
        C[i] =
            2 * C[i - 1] - C[i - 2] + i * dy[i] * dy[i] + 2 * c[i - 1] * dy[i];
    }
    cout << R[n - 1] + C[n - 1] << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}