• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号
登陆 注册

分治法求解最近对问题（c++）

原作者: [db:作者] 来自: [db:来源] 收藏 邀请
#include"stdafx.h"
#include<iostream>
#include<cmath>
#define TRUE 1
#define FALSE 0
using namespace std;
typedef struct Node//坐标点
{
 double x;
 double y;
}Node;  
typedef struct List
{
 Node* data;      //点
 int count;      //点的个数
}List;
typedef struct CloseNode
{
 Node a;
 Node b;     //计算距离的两个点
 double space;     //距离平方
}CloseNode;
int n;     //点的数目
//输入各点到List中
void create(List &L)
{
 cout << "请输入平面上点的数目:\n";
 cin >> n;
 L.count = n;
 L.data = new Node[L.count];      //动态空间分配
 cout << "输入各点坐标 :x_y):" << endl;
 for (int i = 0; i<L.count; ++i)
  cin >> L.data[i].x >> L.data[i].y;
}
//求距离的平方
double square(Node a, Node b)
{
 return ((a.x - b.x)*(a.x - b.x)) + ((a.y - b.y)*(a.y - b.y));
}
//冒泡排序
void BubbleSort(Node r[], int length)
{
 int change, n;
 n = length; change = TRUE;
 double b, c;
 for (int i = 0; i<n - 1 && change; ++i)
 {
  change = FALSE;
  for (int j = 0; j<n - i - 1; ++j)
  {
   if (r[j].x>r[j + 1].x)
   {
    b = r[j].x; c = r[j].y;
    r[j].x = r[j + 1].x; r[j].y = r[j + 1].y;
    r[j + 1].x = b; r[j + 1].y = c;
    change = TRUE;
   }
  }
 }
}
//分治法中先将坐标按X轴从小到大的顺序排列
void paixu(List L)
{
 BubbleSort(L.data, L.count);   //调用冒泡排序
}
//左右各距中线d的区域的最近对算法
void middle(const List & L, CloseNode &cnode, int mid, double midX)
{
 int i, j;    //分别表示中线左边，右边的点
 double d = sqrt(cnode.space);
 i = mid;
 while (i >= 0 && L.data[i].x >= (midX - d))    //在左边的d区域内
 {
  j = mid;
  while (L.data[++j].x <= (midX + d) && j <= L.count)    //在右边的d区域内
  {
   if (L.data[j].y<(L.data[i].y - d) || L.data[j].y>(L.data[i].y + d))   //判断纵坐标是否在左边某固定点的2d区域内
    continue;
   double space = square(L.data[i], L.data[j]);
   if (cnode.space>space)    //在满足条件的区域内依次判断
   {
    cnode.a = L.data[i];
    cnode.b = L.data[j];
    cnode.space = space;
   }
  }
  --i;
 }
}
//分治法求最近对
void DivideConquer(const List &L, CloseNode &closenode, int begin, int end)
{
 if (begin != end)
 {
  int mid = (begin + end) / 2;     //排列后的中间的那个点
  double midX = L.data[mid].x;
  DivideConquer(L, closenode, begin, mid);      //继续在左半边用分治法求最近对
  DivideConquer(L, closenode, mid + 1, end);      //继续在右半边用分治法求最近对
  middle(L, closenode, mid, midX);               //判断左右各距中线d的区域，是否有最近对
 }
}
void main()
{
 //初始化
 List list;
 CloseNode closenode;
 closenode.space = 10000;    
 create(list);    
 cout << "各点坐标为:" << endl;
 for (int i = 0; i<list.count; ++i)
  cout << "X=" << list.data[i].x << "   Y=" << list.data[i].y << "\n";
 cout << "用分治法求最近对:" << endl;
 paixu(list);
 cout << "经过排序后的各点:" << endl;
 for (int j = 0; j<list.count; ++j)
  cout << "X=" << list.data[j].x << "   Y=" << list.data[j].y << "\n";
 DivideConquer(list, closenode, 0, list.count - 1);
 cout << "最近对为点 (" << closenode.a.x << "," << closenode.a.y << ")和点(" << closenode.b.x << "," << closenode.b.y << ")\n" << "最近距离为: " << sqrt(closenode.space) << endl;
}
 

 

鲜花
握手
雷人
路过
鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
More+
上一篇：
codeforces295CGregandFriends（BFS+DP）发布时间：2022-07-13
下一篇：
codeforces792C.DividebyThree发布时间：2022-07-13
热门推荐
More+
热门话题
More+
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服（服务时间 9:00～18:00）

在线QQ客服
地址：深圳市南山区西丽大学城创智工业园
电邮：jeky_zhao#qq.com
移动电话：139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap