本文主要是介绍MT3016 竹鼠通讯，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
在真空中，一块无限平坦光滑绝缘不导热草地上有很多光滑且相同球形竹鼠，它们的坐标为（xi，yi）。竹鼠之间会通过脑电波联系彼此。现在请问相距最近两只竹鼠的直线距离分别是多少（所有竹鼠都在草地的第一象限）？
格式
输入格式：
第一行一个整数n；
接下来 n行每行两个非负浮点数，xi,yi，表示第 i个点的 X 坐标与 Y 坐标。xi,yi都精确到小数点后两位。
输出格式：
一行，一个浮点数，最短距离。精确到小数点后4位。
样例 1
输入：
4 0.0 0.0 0.0 1.0 1.0 0.0 1.0 1.0
输出：
1.0000
备注
其中： 0≤n≤10^5，竹鼠的坐标数据范围在int型范围内。并且可能会有重叠的竹鼠。
思路：模板题，最近点对问题，用分治解决。
即将区域分成 l----mid---r，即最短距离有三种情况：全在左边、全在右边、一个在左一个在右
#include <bits/stdc++.h>
using namespace std;
#define INF 10000000001
const int N = 1e5 + 7;
struct node
{double x, y;
} a[N];
int n, t[N];
double ans = 0;
bool cmp(node &a, node &b)//x,y升序
{if (a.x < b.x)return true;else if (a.x == b.x && a.y < b.y)return true;elsereturn false;
}
bool cmp2(int &i, int &j)
{if (a[i].y < a[j].y) // 按y升序return true;elsereturn false;
}
double dis(int i, int j)
{double c = sqrt((a[i].x - a[j].x) * (a[i].x - a[j].x) + (a[i].y - a[j].y) * (a[i].y - a[j].y));return c;
}
double merge(int l, int r)
{if (l == r)//重叠return INF;if (l == r - 1)return dis(l, r);int mid = (l + r) / 2;double d1 = merge(l, mid);double d2 = merge(mid + 1, r);ans = min(d1, d2); // 求全在左边和全在右边的最小值int k = 0;// 求一左一右的最小值for (int i = l; i <= r; i++){if (fabs(a[i].x - a[mid].x) <= ans) // 将一左一右的编号写入t{t[k] = i;k++;}sort(t, t + k, cmp2);for (int i = 0; i < k; i++){for (int j = i + 1; j < k && a[t[j]].y - a[t[i]].y < ans; j++){ans = min(ans, dis(t[i], t[j]));}}}return ans;
}
int main()
{cin >> n;for (int i = 0; i < n; i++)cin >> a[i].x >> a[i].y;sort(a, a + n, cmp);printf("%.4f", merge(0, n - 1));
}这篇关于MT3016 竹鼠通讯的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
