蚁巢相遇问题

一 问题描述

有 N 个蚁巢，编号为 1～N 。第 i 个蚁巢的位置是(xi , yi)，没有两个蚁巢在同一位置。所有蚂蚁都遵守一些规律：

① 当一只蚂蚁在蚁巣 p 时，它总是移动到离 p 最近的另一个蚁巣，若有多个蚁巣与 p 的距离最小，则它会移动到 x 坐标值较小的蚁巣。若仍有平局，则选择 y 坐标值较小的蚁巣。当蚂蚁从一个蚁巣移动到另一个蚁巣时，它总是沿着连接它们的线段移动。

② 蚂蚁从不停下来，当蚂蚁到达一个蚁巣时，它会立即移动到下一个蚁巣。所以，蚂蚁可以无限次地造访蚁巣。

③ 所有蚂蚁都以同样的速度移动，所有蚂蚁和蚁巢都可被看作点。给定两个不同的蚁巣，求两只蚂蚁同时从这两个蚁巣移动，会不会在某个时间相遇？

二 输入和输出

1 输入

输入以整数 T（T≤10）为开头，表示测试用例的数量。每个测试用例都以整数 N 和 Q （2≤N≤10^5 ，1≤Q≤10^5 ）为开头，分别表示蚁巢数和查询数。下面的 n 行，每行都包含两个整数 Xi 和 Yi （-10^9≤Xi , Yi≤10^9 ），表示第 i 个蚁巢的位置。下面的 Q 行，每行都包含两个整数 i 和 j（1≤i , j≤N ，i≠j ），表示两个给定蚁巢的编号。

2 输出

对每个测试用例，都输出“Case#X :”，其中 X 是用例编号，从 1 开始。然后对每个查询，若两个蚂蚁会相遇，则在一行中输出“YES”，否则输出“NO”。

三 输入和输出样例

1 输入样例

2

2 1

0 0

-1 1

1 2

5 2

1 1

3 3

4 4

0 -3

0 -4

1 3

2 4

2 输出样例

Case #1:

YES

Case #2:

YES

NO

四 分析和设计

1 分析

本问题为二维数据，可采用 KD 树解决。因为蚂蚁总是向最近的蚁巢移动，因此可以将蚁巢与最近的蚁巢合并为一个连通分量，采用并查集实现。查询从两个蚁巢出发的两只蚂蚁是否会相遇时，只需查询两个蚁巢是否在同一个连通分量中。

（1）根据输入数据的二维坐标创建 KD 树。

（2）在 KD 树中查询每个点 p[i] 的最近点，合并两个点为一个连通分量。

（3）对每个查询 x、y，若 x 、y 在同一个连通分量中，则输出“YES”，否则输出“NO”。

2 设计

查询给定点 p 的最近点，直接套用查询距离 p 最近的 m 个点的模板，算法步骤如下。

（1）创建一个序对，第 1 个元素记录当前节点到 p 的距离，第 2 个元素记录当前节点；然后创建一个优先队列，存储离 p 最近的序对，优先队列按距离最大优先。

（2）从树根开始查询，先计算树根与 p 的距离 dis(kd[rt], p)，用 tmp 记录该距离和树根节点。

（3）若 p.x[dim]<kd[rt].x [dim]，则先在 lc 中查询，否则在 rc 中查询。在程序中若判断 p.x [dim]≥kd[rt].x [dim]，则交换 lc 和 rc，这样就可以统一为首先在 lc 中查询。

（4）若 lc 不空，则在 lc 中递归查询 query(lc,m,dep+1, p)。

（5）若队列中的元素个数小于 m ，则直接将 tmp 入队，flag=1，还需要在右子树中查询；否则若判断 tmp 到 p 的距离小于堆顶到 p 的距离，则堆顶出队，tmp 入队。若以 p 为球心且 p 到队列中最远点的距离为半径的超球体与划分点的另一区域有交集（d≤r），则 flag=1，还需要在右子树中查询。

（6）若 rc 不空且 flag=1，则在 rc 中递归查询 query(rc,m,dep+1,p)。

本问题可能有多个点到 p 的距离相同，因此需要对与另一区域有交集的判断条件加等号。若到 p 最近的两个点距离相同，则比较第 1 维的大小，若第 1 维相同，则比较第 2 维的大小，选择坐标小的点作为最近点。如下图所示，G、C 到 p 的距离相同，比较第一维，G 的 x 坐标比 C 的 x 坐标小，选择 G。

五 代码

package com.platform.modules.alg.alglib.hdu5809;import javafx.util.Pair;import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;public class Hdu5809 {private int N = 50010;public String output = "";private final int inf = 0x3f3f3f3f;int idx, n, q, k = 2;int fa[] = new int[N];Node a[] = new Node[N];int sz[] = new int[N << 2];Node kd[] = new Node[N << 2];public Hdu5809() {for (int i = 0; i < a.length; i++) {a[i] = new Node();}}PriorityQueue<Pair<Integer, Node>> que = new PriorityQueue<>(new MyComparator());public String cal(String input) {int T, cas = 0;String[] line = input.split("\n");T = Integer.parseInt(line[0]);int count = 1;while (T-- > 0) {String[] num = line[count++].split(" ");n = Integer.parseInt(num[0]);q = Integer.parseInt(num[1]);for (int i = 0; i < n; i++) {String[] node = line[count++].split(" ");a[i].x[0] = Integer.parseInt(node[0]);a[i].x[1] = Integer.parseInt(node[1]);a[i].id = fa[i] = i;}build(1, 0, n - 1, 0);for (int i = 0; i < n; i++) {query(1, 1, 0, a[i]);Node tmp = que.peek().getValue();int u = find(a[i].id);int v = find(tmp.id);fa[u] = v;while (!que.isEmpty()) que.poll();}output += String.format("Case #%d:\n", ++cas);while (q-- > 0) {int x, y;String[] query = line[count++].split(" ");x = Integer.parseInt(query[0]);y = Integer.parseInt(query[1]);x--;y--; // 编号从0开始if (find(x) == find(y)) {output += "YES\n";} else {output += "NO\n";}}}return output;}int dis(Node p, Node q) {int ret = 0;for (int i = 0; i < k; i++)ret += (p.x[i] - q.x[i]) * (p.x[i] - q.x[i]);return ret > 0 ? ret : inf;}void build(int i, int l, int r, int dep) {if (l > r) return;int mid = (l + r) >> 1;idx = dep % k;sz[i] = 1;sz[i << 1] = sz[i << 1 | 1] = 0;Arrays.sort(a, l, r + 1);kd[i] = a[mid];build(i << 1, l, mid - 1, dep + 1);build(i << 1 | 1, mid + 1, r, dep + 1);}void query(int rt, int m, int dep, Node p) {if (sz[rt] == 0) return;Pair<Integer, Node> tmp = new Pair(dis(kd[rt], p), kd[rt]);int lc = rt << 1, rc = rt << 1 | 1, dim = dep % k, flag = 0;if (p.x[dim] >= kd[rt].x[dim]) {int temp = lc;lc = rc;rc = temp;}if (sz[lc] > 0)query(lc, m, dep + 1, p);if (que.size() < m) {que.add(tmp);flag = 1;} else {if (tmp.getKey() < que.peek().getKey()) {que.poll();que.add(tmp);}if ((p.x[dim] - kd[rt].x[dim]) * (p.x[dim] - kd[rt].x[dim]) <= que.peek().getKey())//注意有=号,可能有多个点有相同距离flag = 1;}if (sz[rc] > 0 && flag == 1)query(rc, m, dep + 1, p);}int find(int x) {if (fa[x] == x) {return x;} else {fa[x] = find(fa[x]);return fa[x];}}class Node implements Comparable<Node> {int x[] = new int[2];int id;public int compareTo(Node o) {for (int i = 0; i < k; i++)if (x[i] != o.x[i]) return x[i] > o.x[i] ? 1 : -1; // 升序return 0;}}class MyComparator implements Comparator<Pair<Integer, Node>> {@Overridepublic int compare(Pair<Integer, Node> num1, Pair<Integer, Node> num2) {return num2.getKey().compareTo(num1.getKey());}}
}

 六 测试