1. 距离之和

设 $(x,y)$ 与 $(x’,y’)$ 是平面上的两个点的坐标，它们之间的城市距离定义为

$$ |x-x’| + |y-y’| $$

给定 $n$ 个点，请计算任意两点的城市距离之和。

限制：

• $1 \leqslant n \leqslant 3 \times 10^5$
• $-10^6 \leqslant x_i, y_i \leqslant 10^6$

算法分析

可以将 $x$ 坐标和 $y$ 坐标分开考虑
只讲 $x$ 坐标的处理方法，$y$ 坐标同理
先将所有点 $x$ 的坐标排序，那么点 $i$ 对前面 $i-1$ 个点会贡献 $x_i$，对后面 $n-i$ 个点会贡献 $-x_i$

代码实现

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

ll f(vector<int> xs) {
    int n = xs.size();
    sort(xs.begin(), xs.end());
    ll res = 0;
    rep(i, n) {
        ll co = +i-(n-i-1);
        res += co*xs[i];
    }
    return res;
}

int main() {
    int n;
    cin >> n;

    vector<int> x(n), y(n);
    rep(i, n) cin >> x[i] >> y[i];

    ll ans = f(x) + f(y);
    cout << ans << '\n';

    return 0;
}

2. ABC351E

考虑将切比雪夫坐标系转成曼哈顿坐标系，$(x, y) \to (\frac{x+y}{2}, \frac{x-y}{2})$
另外，原图上从点 $(x_1, y_1)$ 能到达点 $(x_2, y_2)$ 当且仅当这两个点的曼哈顿距离为偶数，那么旋转之后就变成了 $x_1+y_1$ 和 $x_2+y_2$ 的奇偶性要相同
然后就变成上面的题了

代码实现

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

ll f(vector<int> xs) {
    int n = xs.size();
    sort(xs.begin(), xs.end());
    ll res = 0;
    rep(i, n) {
        ll co = +i-(n-i-1);
        res += co*xs[i];
    }
    return res/2;
}

int main() {
    int n;
    cin >> n;

    vector<vector<int>> xs(2), ys(2);
    rep(i, n) {
        int X, Y;
        cin >> X >> Y;
        int x = X+Y;
        int y = X-Y;
        xs[x%2].push_back(x);
        ys[x%2].push_back(y);
    }

    ll ans = 0;
    rep(i, 2) ans += f(xs[i]) + f(ys[i]);

    cout << ans << '\n';

    return 0;
}

3. Max Manhattan Distance

给定平面上的 $N$ 个点，$P_1, P_2, \cdots, P_N$，点 $P_i$ 的坐标为 $(x_i, y_i)$

按顺序处理以下 $Q$ 个询问：

• 给定整数 $q_i$，求出点 $P_{q_i}$ 到平面上上其他点的曼哈顿距离的最大值

限制：

• $2 \leqslant N \leqslant 10^5$
• $1 \leqslant Q \leqslant N$
• $-10^9 \leqslant x_i, y_i \leqslant 10^9$

算法分析

考虑将曼哈顿坐标系转成切比雪夫坐标系 $(x, y) \to (x+y, x-y)$

代码实现

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

inline void chmin(ll& x, ll y) { if (x > y) x = y; }
inline void chmax(ll& x, ll y) { if (x < y) x = y; }

int main() {
    int n, q;
    cin >> n >> q;

    vector<ll> a(n), b(n);
    const ll INF = 1e18;
    ll min_a = INF, max_a = 0, min_b = INF, max_b = 0;
    rep(i, n) {
        ll x, y;
        cin >> x >> y;
        ll X = x+y;
        ll Y = x-y;
        a[i] = X;
        b[i] = Y;
        chmin(min_a, X);
        chmax(max_a, X);
        chmin(min_b, Y);
        chmax(max_b, Y);
    }

    rep(qi, q) {
        int i;
        cin >> i;
        --i;
        ll ans = 0;
        chmax(ans, abs(a[i]-min_a));
        chmax(ans, abs(a[i]-max_a));
        chmax(ans, abs(b[i]-min_b));
        chmax(ans, abs(b[i]-max_b));
        cout << ans << '\n';
    }

    return 0;
}

4. 多边形的面积

给出一个没有缺口的简单多边形，它的边是垂直或者水平的，要求计算多边形的面积。

多边形被放置在一个 $xOy$ 的笛卡尔平面上，它所有的边都平行于两条坐标轴之一。然后按逆时针方向给出各顶点的坐标值。所有的坐标值都是整数，因此多边形的面积也为整数。

限制：

• $1 \leqslant n \leqslant 100$
• $-200 \leqslant x, y \leqslant 200$

算法分析

对于每条边 $\overrightarrow{AB}$，累加 $\frac{\overrightarrow{OA} \times \overrightarrow{OB}}{2}$，最后得到的结果即为多边形的面积

代码实现

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

struct Point {
    int x, y;
    Point(int x=0, int y=0): x(x), y(y) {}
    int cross(const Point& o) const { return x*o.y - y*o.x; }
};

int main() {
    int n;
    cin >> n;

    vector<Point> ps(n);
    rep(i, n) cin >> ps[i].x >> ps[i].y;

    int ans = 0;
    rep(i, n) {
        ans += ps[i].cross(ps[(i+1)%n]);
    }
    ans /= 2;

    cout << ans << '\n';

    return 0;
}