文章出處
文章列表
|
#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;
}
|
文章列表
全站熱搜
留言列表
