算法竞赛进阶指南-32.袭击 - Be Grinder,for Better

题目链接

算法竞赛进阶指南-32.袭击

在与联盟的战斗中屡战屡败后，帝国撤退到了最后一个据点。

依靠其强大的防御系统，帝国击退了联盟的六波猛烈进攻。

经过几天的苦思冥想，联盟将军亚瑟终于注意到帝国防御系统唯一的弱点就是能源供应。

该系统由 $N$ 个核电站供应能源，其中任何一个被摧毁都会使防御系统失效。

将军派出了 $N$ 个特工进入据点之中，打算对能源站展开一次突袭。

不幸的是，由于受到了帝国空军的袭击，他们未能降落在预期位置。

作为一名经验丰富的将军，亚瑟很快意识到他需要重新安排突袭计划。

他现在最想知道的事情就是哪个特工距离其中任意一个发电站的距离最短。

你能帮他算出来这最短的距离是多少吗？

输入格式

输入中包含多组测试用例。

第一行输入整数 $T$ ，代表测试用例的数量。

对于每个测试用例，第一行输入整数 $N$ 。

接下来 $N$ 行，每行输入两个整数 $X$ 和 $Y$ ，代表每个核电站的位置的 $X，Y$ 坐标。

在接下来 $N$ 行，每行输入两个整数 $X$ 和 $Y$ ，代表每名特工的位置的 $X，Y$ 坐标。

输出格式

每个测试用例，输出一个最短距离值，结果保留三位小数。

每个输出结果占一行。

数据范围

$1 \le N \le 100000$ ,
$0 \le X,Y \le 1000000000$

输入样例：

输出样例：

1.414
0.000

Method : 分治

关于计算几何的平面最近点对问题，有如下经典永流传系列：

P1257.平面最近点对

P1429 平面最近点对（加强版）

P7883 平面最近点对（加强加强版）

本题就是这道题的一个小拓展，把点划分成了两个集合，只允许先从两个集合分别选出一个点，再来计算距离。
那么可以在计算前判断两个点的类型，如果同属一个集合，那么把其距离视为无穷大即可。

另外本题的测试数据很刁钻，需要额外加一个按rand排序，把序列中集合的点的分布打乱，不然会TLE。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <stdlib.h>

using namespace std;

typedef long long LL;

const LL INF = 1e18;
const int N = 1e5 + 7;

struct Node {
    int x;
    int y;
    int rd;
    int type;
    bool operator < (Node& rhs) const {
        if (x == rhs.x) return rd < rhs.rd;
        else return x < rhs.x;
    }
};

Node p[N * 2];
Node tmp[N * 2];

double dis(Node& a, Node& b) {
    if (a.type == b.type) return INF;
    LL dx = a.x - b.x;
    LL dy = a.y - b.y;
    return sqrt(dx * dx + (LL)dy * dy);
}

double divide(int l, int r) {
    if (l == r) return INF;
    if (r - l == 1) return dis(p[l], p[r]);
    
    int mid = l + (r - l) / 2;
    double dl = divide(l, mid), dr = divide(mid + 1, r);
    double d = min(dl, dr);
    
    int k = 0;
    for (int i = l; i <= r; i ++) {
        if (abs(p[i].x - p[mid].x) < d) {
            tmp[k ++] = p[i];
        }
    }
    sort(tmp, tmp + k, [](Node& a, Node& b) -> bool{
        return a.y < b.y;
    });
    
    for (int i = 0; i < k; i ++) {
        for (int j = i + 1; j < k && abs(tmp[i].y - tmp[j].y) < d; j ++) {
            d = min(d, dis(tmp[i], tmp[j]));
        }
    }
    
    return d;
}

int main() {
    srand(0);
    int T;
    cin >> T;
    
    while (T --) {
        int n;
        scanf("%d", &n);
        for (int i = 1; i <= n * 2; i ++) {
            scanf("%d %d", &p[i].x, &p[i].y);
            p[i].rd = rand()%3000000;
            if (i <= n) p[i].type = 1;
            else p[i].type = 2;
        }
        sort(p + 1, p + 1 + n * 2);
        printf("%.3f\n", divide(1, n * 2));
    }
    
    return 0;
}

复杂度分析

时间复杂度 ${O(n\log^2n)}$ ，。整个代码的瓶颈就在 sort 上了, 时间复杂度为 $T(n)=2 \cdot T\left(\frac{n}{2}\right)+O(n \log n)=O\left(n \log ^2 n\right)$ , 当然如果使用归并排序替换 sort 的话, 就可以做到严格的 $O(n \log n)$ 。
空间复杂度 ${O(1)}$ 。

补充

P1429 平面最近点对（加强版）

P1429题解:

不难发现 $\mathrm{P}_j$ 满足这些条件:

$\mathrm{P}_j$ 与 mid 线的距离小于 $d$ 。
$\mathrm{P}_j$ 的纵坐标比 $P_i$ 大 (因为如果 $\mathrm{P}_j$ 的纵坐标比 $\mathrm{P}_i$ 小, 则这个状态会在之前考虑有哪些点可能与 $\mathrm{P}_j$ 形成最近公共点对的时候考虑到, 没必要重复考虑, 虽然真的考虑的话也就只是 2 倍常数）。
$\mathrm{P}_j$ 和 $\mathrm{P}_i$ 的纵坐标之差小于 $d$ 。

根据这三条, 我们可以画出一个 $d \times 2 d$ 的矩形, 合法的 $\mathrm{P}_j$ 一定是在这个矩形中的（不含边界）。
但是, 我们又知道, 如果两个点同在左侧, 则距离 $\geq d$ ; 如果两个点同在右侧, 则距离 $\geq d$ 。
那么, 无论是 $\operatorname{mid}$ 左边的正方形还是右边的正方形, 每个里面都至多放 3 个点（包括 $\mathrm{P}_i$ ）。
图中红色点即代表 $\mathrm{P}_j$ , 展示了一种方案, 其中每条虚线边的长度都 $\geq d$ 。
所以对于每个 $\mathrm{P}_i$ , 检验至多其他 5 个点即可, 所以求最近点对的部分时间复杂度是 $O(n)$ 的!
(当然其实与 $\mathrm{P}_i$ 同侧的 $\mathrm{P}_j$ 是不可能对更新答案有用的, 如果你愿意的话, 检验至多 3 个点即可)

注意一点，为什么中间线是p[mid].x而不是(p[l].x + p[r].x )/ 2？

因为递归左右就是按照p的下标来分治的，因此实际划分的左右区间长度本来就不一样，中间分界线就是p[mid].x

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long LL;
const int N = 4e5 + 7;
const int INF = 0x3f3f3f3f;

struct Node {
	double x;
	double y;
	bool operator < (const Node& rhs) const {
		if (x == rhs.x) return y < rhs.y;
		return x < rhs.x;
	}
};
Node p[N];
Node tmp[N];

double dis(Node& a, Node& b) {
	double dx = a.x - b.x;
	double dy = a.y - b.y;
	return sqrt(dx * dx + dy * dy);
}

double divide(int l, int r) {
	if (l == r) return INF;
	if (r - l == 1) return dis(p[l], p[r]);

	// 分治
	int mid = l + (r - l) / 2;
	double dl = divide(l, mid), dr = divide(mid + 1, r);

	// 归并
	double d = min(dl, dr);
	int k = 0;
	for (int i = l; i <= r; i++) {
		if (fabs(p[mid].x - p[i].x) < d) {
			tmp[++k] = p[i];
		}
	}

	sort(tmp + 1, tmp + 1 + k, [](Node& a, Node& b) -> bool {
		return a.y < b.y;
	});
	for (int i = 1; i <= k; i++) {
		for (int j = i + 1; j <= k && (tmp[j].y - tmp[i].y) < d; j++) {
			d = min(d, dis(tmp[i], tmp[j]));
		}
	}
	return d;
}


int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		scanf("%lf %lf", &p[i].x, &p[i].y);
	}
	sort(p + 1, p + 1 + n);
	printf("%.4lf", divide(1, n));

	return 0;
}

P7883 平面最近点对（加强加强版）

P7883 题解：

这题别求 $sqrt$ ，会退化到 $O(nlog^2(n))$ 从而TLE.

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;
const int N = 4e5 + 7;
const LL INF = 1e18;

struct Node {
	LL x;
	LL y;
	bool operator < (const Node& rhs) const {
		if (x == rhs.x) return y < rhs.y;
		return x < rhs.x;
	}
};
Node p[N];
Node tmp[N];

LL dis(Node& a, Node& b) {
	double dx = a.x - b.x;
	double dy = a.y - b.y;
	return dx * dx + dy * dy;
}

LL divide(int l, int r) {
	if (l == r) return INF;
	if (r - l == 1) return dis(p[l], p[r]);

	// 分治
	int mid = l + (r - l) / 2;
	LL dl = divide(l, mid), dr = divide(mid + 1, r);

	// 归并
	LL d = min(dl, dr);
	int k = 0;
	for (int i = l; i <= r; i++) {
		if (abs(p[mid].x - p[i].x) * abs(p[mid].x - p[i].x) < d) {
			tmp[++k] = p[i];
		}
	}
	sort(tmp + 1, tmp + 1 + k, [](Node& a, Node& b) -> bool {
		return a.y < b.y;
	});

	for (int i = 1; i <= k; i++) {
		for (int j = i + 1; j <= k && (tmp[j].y - tmp[i].y) * (tmp[j].y - tmp[i].y) < d; j++) {
			d = min(d, dis(tmp[i], tmp[j]));
		}
	}
	return d;
}


int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		scanf("%lld %lld", &p[i].x, &p[i].y);
	}
	sort(p + 1, p + 1 + n);
	LL res = divide(1, n);
	printf("%lld", res);

	return 0;
}

参考:

https://www.luogu.com.cn/blog/syksykCCC/solution-p1429

https://www.acwing.com/solution/content/119700/

算法竞赛进阶指南

Algorithm C++ 分治

本博客所有文章均采用 CC BY-NC-SA 4.0 协议，禁止商用，转载请注明出处！

算法竞赛进阶指南-33.防线上一篇

算法竞赛进阶指南-31.分形下一篇