Points

发表于 2023-06-14 分类于 codeforces ， practice

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

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

$1 \leq n \leq 10^{5}$

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 \leq n \leq 10^{5}$

solution

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

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

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

举个例子来说，如果给出的坐标为 $(x 1, y 1), (x 2, y 2), (x 3, y 3)$

答案应当是 $(x 2 - x 1)^{2} + (y 2 - y 1)^{2} + (x 3 - x 1)^{2} + (y 3 - y 1)^{2} + (x 3 - x 2)^{2} + (y 3 - y 2)^{2}$

可以拆分为 $(x 2 - x 1)^{2} + (x 3 - x 1)^{2} + (x 3 - x 2)^{2}$ 和 $(y 2 - y 1)^{2} + (y 3 - y 1)^{2} + (y 3 - y 2)^{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}, \dots, x_{i + 1}$ 中任意两个点之间的距离平方和。

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

我们观察一个例子 $d x_{1} = a, d x_{2} = b, d x_{3} = c, d x_{4} = d$

$R_{1} = a^{2}$

$R_{2} = R_{1} + (a + b)^{2} + b^{2} = R_{1} + 2 b^{2} + 2 a b + a^{2}$

$R_{3} = R_{2} + (a + b + c)^{2} + (b + c)^{2} + c^{2} = R_{2} + 3 c^{2} + 2 (a + 2 b) 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} + 4 d^{2} + 2 (a + 2 b + 3 c) d + R_{3} - R_{2}$

通过观察得到递推式 $R_{i} = 2 R_{i - 1} - R_{i - 2} + i \cdot d x_{i}^{2} + 2 r_{i} d x_{i}$ ，其中 $R_{0} = 0, R_{1} = d x_{1}^{2}$ 。 $r_{i} = \sum_{j = 1}^{i} j \cdot d x_{j}$ 。

对于n个点的y值同理可以定义状态 $C_{i}$ 为 $y_{1}, y_{2}, \dots, y_{i + 1}$ 中任意两个点之间的距离平方和。 $d y_{i} = y_{i + 1} - y_{i}, c_{i} = \sum_{j = 1}^{i} j \cdot d y_{j}$ 。得到递推式 $C_{i} = 2 C_{i - 1} - C_{i - 2} + i \cdot d y_{i}^{2} + 2 c_{i} d y_{i}$ ，其中 $C_{0} = 0, C_{1} = d y_{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;
}