距离转化

cqbzlzm · 2024-02-29 23:02:51 · 算法·理论

做不动题来，来颓废

距离转化

参考洛谷日报。

定义

欧氏距离：d(A,B)=\sqrt{(x_x-x_1)^2+(y_2-y_1)^2}
曼哈顿距离：d(A,B)=|x_1-x_2|+|y_1-y_2|
切比雪夫距离：d(A,B)=\max(|x_1-x_2|,|y_1-y_2|)

欧式距离就是两点间的直线距离，曼哈顿就是只能上下左右走的距离，切比雪夫距离就是可以8个方向走的距离。

转化

当我们把 (x,y) 转为 (\frac{x+y}{2},\frac{x-y}{2})，原坐标系中的 切比雪夫距离 等于新坐标系中的 曼哈顿距离。
当我们把 (x,y) 转为 (x+y,x-y)，原坐标系中的 曼哈顿距离 等于新坐标系中的 切比雪夫距离。

对于整点的问题，我们发现曼哈顿距离的坐标系中的整点在切比雪夫的坐标系中也一定是整点，反之则不成立。因此我们可能需要分类讨论。

例题

Cave Cows 3

我们直接把曼哈顿距离换成切比雪夫距离，然后分别求个横纵坐标的最大最小值就好了。

#include <bits/stdc++.h>
using namespace std;
int n;
int a = INT_MIN, b = INT_MAX, c = INT_MIN, d = INT_MAX;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++) {
        int x, y;
        scanf("%d%d", &x, &y);
        x = x + y, y = x - y - y;
        a = max(a, x); b = min(b, x);
        c = max(c, y); d = min(d, y);
    }
    printf("%d\n", max(a - b, c - d));
    return 0;
}

松鼠聚会

我们把切比雪夫距离转换成曼哈顿距离，然后拆开绝对值，用前缀和算即可。

代码中为了避免小数，给每个坐标乘了个2，所以最后要除掉。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e5;
struct node {
    int x, y;
} a[MAXN + 5];
int n;
int x[MAXN + 5], y[MAXN + 5];
int sum[MAXN + 5], sum1[MAXN + 5];
signed main() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; i ++) {
        int xx, yy;
        scanf("%lld%lld", &xx, &yy);
        x[i] = a[i].x = xx + yy;
        y[i] = a[i].y = xx - yy;
    }
    sort(x + 1, x + n + 1);
    sort(y + 1, y + n + 1);
    for (int i = 1; i <= n; i ++) {
        sum[i] = sum[i - 1] + x[i];
        sum1[i] = sum1[i - 1] + y[i];
    }
    int ans = LONG_LONG_MAX;
    for (int i = 1; i <= n; i ++) {
        int pos = lower_bound(x + 1, x + n + 1, a[i].x) - x;
        int pos1 = lower_bound(y + 1, y + n + 1, a[i].y) - y;
        int ret = 0;
        ret += sum[n] - sum[pos] - a[i].x * (n - pos) + a[i].x * pos - sum[pos];
        pos = lower_bound(y + 1, y + n + 1, a[i].y) - y;
        ret += sum1[n] - sum1[pos1] - a[i].y * (n - pos1) + a[i].y * pos1 - sum1[pos];
        ans = min(ans, ret);
    }
    printf("%lld\n", ans / 2);
    return 0;
}

Dominance

还是一样，把曼哈顿距离转换成切比雪夫距离，那么辐射范围变成了一个矩形，我们可以轻易地用 O(n^2) 的扫描线进行解答。但是因为这道题坐标是整点，而转换会出现小数，我们考虑如何避免小数。

对于转换后的的点 (x,y)，它在转换前是 (\frac{x+y}{2},\frac{x-y}{2})，我们们发现有些点虽然可能在转换后是整点，但转换前不是，只有转换后奇偶性相同的点转换前才是整点。

所以我们要单独维护转换后 x,y 同为奇数或同为偶数的点的数量。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 3e3;
int n, m, p;
int cl;
struct line {
    int x, y1, y2, d;
} a[MAXN * 2 + 5];
int recnt, re[MAXN * 2 + 5];
struct node {
    int o, e;
};
node get(int l, int r) {
    return {(r - l + 1) / 2 + (((r - l + 1) & 1) & (r & 1)), (r - l + 1) / 2 + (((r - l + 1) & 1) & !(r & 1))};
}
int b[MAXN + 5];
node W, B, answ, ansb;
int find(int x) {
    return lower_bound(re + 1, re + 1 + recnt, x) - re;
}
signed main() {
    scanf("%lld%lld%lld", &n, &m, &p);
    for (int i = 1; i <= p; i ++) {
        char ch; cin >> ch;
        int x, y, d; scanf("%lld%lld%lld", &x, &y, &d);
        x = x + y; y = x - 2 * y;
        a[++ cl] = {x - d, y - d, y + d + 1, (ch == 'W') ? 1 : -1};
        a[++ cl] = {x + d + 1, y - d, y + d + 1, (ch == 'W') ? -1 : 1};
        re[++ recnt] = y - d;
        re[++ recnt] = y + d + 1;
    }
    sort(re + 1, re + 1 + recnt); recnt = unique(re + 1, re + 1 + recnt) - re - 1;
    sort(a + 1, a + 1 + cl, [](line a, line b) {return a.x < b.x; });
    for (int i = 1; i <= cl; i ++) {
        node cur = get(a[i - 1].x, a[i].x - 1);
        answ.e += cur.e * W.e, answ.o += cur.o * W.o;
        ansb.e += cur.e * B.e, ansb.o += cur.o * B.o;
        int Y1 = find(a[i].y1), Y2 = find(a[i].y2);
        for (int j = Y1; j < Y2; j ++) {
            cur = get(re[j], re[j + 1] - 1);
            if (b[j] == 0 && a[i].d == -1) B.e += cur.e, B.o += cur.o;
            if (b[j] == 0 && a[i].d == 1) W.e += cur.e, W.o += cur.o;
            if (b[j] == 1 && a[i].d == -1) W.e -= cur.e, W.o -= cur.o;
            if (b[j] == -1 && a[i].d == 1) B.e -= cur.e, B.o -= cur.o;
            b[j] += a[i].d;
        }
    }
    printf("%lld %lld", answ.e + answ.o, ansb.e + ansb.o);
    return 0;
}

Four Coloring

首先把曼哈顿距离转换成切比雪夫距离，然后把新坐标系的整点按照 d\times d 的矩形进行分割，得到的图形按如图进行涂色：

所以代码如下：

#include <bits/stdc++.h>
using namespace std;
signed main() {
    int n, m, d;
    scanf("%d%d%d", &n, &m, &d);
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) {
            int x = i + j + 114514, y = i - j + 114514;
            if (((x / d) % 2) * 2 + (y / d) % 2 == 0) putchar('R');
            if (((x / d) % 2) * 2 + (y / d) % 2 == 1) putchar('Y');
            if (((x / d) % 2) * 2 + (y / d) % 2 == 2) putchar('G');
            if (((x / d) % 2) * 2 + (y / d) % 2 == 3) putchar('B');
        }
        putchar('\n');
    }
    return 0;
}

P2906

先把曼哈顿距离转换为切比雪夫距离，然后按照 x 坐标排序，用指针维护一个 x 坐标差小于等于 C 的区间，然后用 set 来维护 y。显然每次我们合并在 y 上的前驱后继即可。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e5;
struct node {
    int x, y;
    friend bool operator < (node a, node b) {
        return a.x < b.x || a.x == b.x && a.y < b.y;
    }
}a[MAXN + 5];
int n, C;
int fa[MAXN + 5], cnt[MAXN + 5];
set<node> s;
int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
bool merge(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy) return 0;
    fa[fx] = fy;
    cnt[fy] += cnt[fx];
    return 1;
}
signed main() {
    scanf("%lld%lld",&n, &C);
    for (int i = 1; i <= n; i ++) {
        int x, y;
        scanf("%lld%lld", &x, &y);
        a[i] = {x + y, x - y};
    }
    for (int i = 1; i <= n; i ++) fa[i] = i, cnt[i] = 1;
    sort(a + 1, a + 1 + n);
    s.insert((node){-(1ll<<60), 0}), s.insert((node){(1ll<<60), 114514});
    s.insert((node){a[1].y, 1});
    int L = 1;
    for (int i = 2; i <= n; i ++) {
        while (a[i].x - a[L].x > C) s.erase(s.lower_bound((node){a[L].y, L})), L ++;
        auto it = s.lower_bound((node){a[i].y, 0});
        if (it->x - a[i].y <= C) merge(i, it->y);
        -- it;
        if (a[i].y - it->x <= C) merge(i, it->y);
        s.insert((node){a[i].y, i});
    }
    int ans = 0, mx = 0;
    for (int i = 1; i <= n; i ++)
        if(find(i) == i) {
            ans ++;
            mx = max(mx, cnt[i]);
        }
    printf("%lld %lld",ans, mx);
    return 0;
}