两个点集各取一个点,使距离最小
两个 最小 距离 一个点
2023-09-14 08:56:53 时间
题目连接 https://www.acwing.com/problem/content/121/
输入样例:
2
4
0 0
0 1
1 0
1 1
2 2
2 3
3 2
3 3
4
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0
输出样例:
1.414
0.000
https://www.cnblogs.com/-citywall123/p/13174180.html
参考上篇博客,平面最小点集的变形,把不同集合点标记一下,只有不同集合的两个点才可以求距离,否则返回距离为无穷
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; const double inf = 1e20; const int maxn = 100005; struct Point { double x, y; int Type; }point[maxn]; int n, mpt[maxn]; //以x为基准排序 bool cmpxy(const Point& a, const Point& b) { if (a.x != b.x) return a.x < b.x; return a.y < b.y; } bool cmpy(const int& a, const int& b) { return point[a].y < point[b].y; } double min(double a, double b) { return a < b ? a : b; } //求两点距离 double dis(int i, int j) { //只有不同集合的点可以求距离 if (point[i].Type == point[j].Type)return inf; return sqrt((point[i].x - point[j].x)*(point[i].x - point[j].x) + (point[i].y - point[j].y)*(point[i].y - point[j].y)); } //将平面二分为左右两个点集,分别找平面左右两边中最短的距离d //然后再把平面区间在[left,right]范围内的点中,把p.x到中点mid距离小于d的点标记 //被标记的点按x坐标再次排序 //两个for遍历这个点集,更新最小距离d double Closest_Pair(int left, int right) { double d = inf; if (left == right) return d; if (left + 1 == right) return dis(left, right); int mid = (left + right) >> 1; double d1 = Closest_Pair(left, mid); double d2 = Closest_Pair(mid + 1, right); d = min(d1, d2); int i, j, k = 0; //分离出宽度为d的区间 for (i = left; i <= right; i++) { if (fabs(point[mid].x - point[i].x) <= d) mpt[k++] = i; } sort(mpt, mpt + k, cmpy); //线性扫描 for (i = 0; i < k; i++) { for (j = i + 1; j < k && point[mpt[j]].y - point[mpt[i]].y < d; j++) { double d3 = dis(mpt[i], mpt[j]); if (d > d3) d = d3; } } return d; } int main() { int t; cin >> t; while (t--) { int n; cin >> n; for (int i = 0; i < n; i++) { scanf("%lf %lf", &point[i].x, &point[i].y); point[i].Type = 0; } for (int i = n; i < n * 2; i++) { scanf("%lf %lf", &point[i].x, &point[i].y); point[i].Type = 1; } n = n * 2; sort(point, point + n, cmpxy); printf("%.3lf\n", Closest_Pair(0, n - 1) ); } return 0; }
相关文章
- 7-9 集合相似度 给定两个整数集合,它们的相似度定义为:N c /N t ×100%。其中N c 是两个集合都有的不相等整数的个数,N t 是两个集合一共有的不相「建
- 三种算法求两个正整数的最大公约数和最小公倍数;求三个数的最大公约数和最小公倍数「建议收藏」
- C语言——求两个数的最大公约数和最小公倍数
- 【Python实践-1】求一元二次方程的两个解[通俗易懂]
- 给定一个头结点为 head 的非空单链表,返回链表的中间结点,如果有两个中间结点,则返回第二个中间结点。
- OpenSSL 修复了两个高危漏洞
- 【字节码插桩】Android 签名机制 ( 生成 Android 签名文件 | 分析签名文件 | 签名文件两个密码的作用 | 三种签名方式 )
- 输入两个正整数m和n,求其最大公约数和最小公倍数详解编程语言
- Oracle查询:从多个表获取数据(oracle查询两个表)
- 同步实现两个MySQL数据库同步(2个mysql数据库)
- Chrome 用户请尽快更新:谷歌发现两个严重的零日漏洞
- MySQL实现两个字段分组查询(mysql两个字段分组)
- Oracle中计算两个日期之和(oracle两个日期相加)
- Oracle计算两数之差(oracle两个数的减法)
- 和Oracle数据库中两数相加的实现(oracle两个数加)
- Oracle两个库表比对分析差异结果(oracle两个库表比对)
- Oracle两值除以无穷大的可能性(oracle两个值除以)
- Oracle两个IP端口完全相同(oracle两个ip相等)
- jquery得到当前页面高度和宽度的两个函数
- ajax完美实现两个网页分页功能的实例代码
- 使用PHP求两个文件的相对路径