資源簡介
按課本算法做出來的,請求大家指教,因為是作業(yè)所以有不必要的界面輸出,請只研究核心代碼。

代碼片段和文件信息
?#include?
#include?
#include?
#include?
#include?
#include?
using?namespace?std;
const?int?N?=?100005;
const?double?MAX?=?10e10;
const?double?eps?=?0.00001;
struct?Point
{
double?x?y;
int?index;
}?;
Point?a[N]?b[N]?c[N];
double?closest(Point?*?Point?*?Point?*?int?int);
double?dis(Point?Point);
int?cmp_x(const?void?*?const?void*);
int?cmp_y(const?void?*?const?void*);
int?merge(Point?*?Point?*?int?int?int);
inline?double?min(double?double);
int?ClosestPoints(intPoint?*int?&int?&);
int?main()
{
int?n?i;
float?de;
int?index1=0index2=0index3=0index4=0;
char?choicechoice2;
do
{
system(“cls“);
cout<<“┌─────────────────────┐“< cout<<“│實驗:最近對問題??????????????????????????│“< cout<<“│系別:計算機工程系????????????????????????│“< cout<<“│班級:07級計算機科學(xué)與技術(shù)2班?????????????│“< cout<<“│姓名:劉菲菲??????????????????????????????│“< cout<<“│學(xué)號:200630891032????????????????????????│“< cout<<“└─────────────────────┘“< cout< cin>>n;
cout<<“輸入坐標格式為3?4即(34)“< for?(i?=?0;?i?{
cout<<“第“<cin>>a[i].x>>a[i].y;
}
cout<<“請選擇運算方法“< cout<<“1.蠻力法?2.分治法?3.結(jié)束:“;
do
{
cin>>choice;
if?(choice?==?‘1‘)?
{e?=?sqrt(ClosestPoints(naindex1index2));
cout<<“第“< cout<<“蠻力法算出最近點對距離為“< }
else?if(choice?==?‘2‘)?
{
qsort(a?n?sizeof(a[0])?cmp_x);
for?(i?=?0;?i?a[i].index?=?i;
memcpy(b?a?n?*sizeof(a[0]));
qsort(b?n?sizeof(b[0])?cmp_y);
d?=?sqrt(closest(a?b?c?0?n?-?1));
cout?<<“分治法算出最近點對距離為“< }
else?if(choice?==?‘3‘)
break;
else?cout<<“選擇錯誤,請重新選擇“;
}while(choice!=‘3‘);
cout<<“是否結(jié)束程序結(jié)束結(jié)束請按n繼續(xù)請按任意鍵“< cin>>choice2;
}while(?choice2!=‘n‘?)?;
return?0;
}
int?ClosestPoints(int?nPoint?a[]int?&index1int?&index2)//蠻力法
{
int?ijd;
int?minDist=60000;
for(i=1;i for(j=i+1;j<=n;j++)
{
d=(a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y);
if(d {minDist=d;
index1=i;
index2=j;
}
}
return?minDist;
}
double?closest(Point?a[]?Point?b[]?Point?c[]?int?p?int?q)//分治法
{
if?(q?-?p?==?1)
return?dis(a[p]?a[q]);
if?(q?-?p?==?2)
{
double?x1?=?dis(a[p]?a[q]);
double?x2?=?dis(a[p?+?1]?a[q]);
double?x3?=?dis(a[p]?a[p?+?1]);
if?(x1?return?x1;
else?if?(x2?return?x2;
else
return?x3;
}
int?m?=?(p?+?q)?/?2;
int?i?j?k;
double?d1?d2;
for?(i?=?p?j?=?p?k?=?m?+?1;?i?<=?q;?i++)
if?(b[i].index?<=?m)
c[j++]?=?b[i];
//數(shù)組c左半部保存劃分后左部的點?且對y是有序的.
else
c[k++]?=?b[i];
d1?=?closest(ac?b?p?m);
d2?=?closest(a?cb?m?+?1?q);
double?dm?=?min(d1?d2);
merge(b?c?p?m?q);?//數(shù)組c左右部分分別是對y坐標有序的?將其合并到b.
for?(i?=?p?k?=?p;?i?<=?q;?i++)
if?(fabs(b[i].x?-?b[m].x)?c[k++]?=?b[i];
//找出離劃分基準左右不超過
?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????文件??????82944??2009-10-29?18:00??最近點對問題\Debug\vc60.idb
?????文件?????110592??2009-10-29?17:56??最近點對問題\Debug\vc60.pdb
?????文件?????598099??2009-10-29?17:56??最近點對問題\Debug\test1.exe
?????文件????1147904??2009-10-29?17:56??最近點對問題\Debug\test1.pdb
?????文件????2034296??2009-10-29?00:51??最近點對問題\Debug\test1.pch
?????文件?????274678??2009-10-29?17:56??最近點對問題\Debug\test1.obj
?????文件?????829568??2009-10-29?17:56??最近點對問題\Debug\test1.ilk
?????文件????????244??2009-10-29?18:00??最近點對問題\test1.plg
?????文件???????5118??2009-10-24?18:25??最近點對問題\test1.vcproj
?????文件???????1427??2009-10-24?18:25??最近點對問題\test1.vcproj.KURORO-4B2C31F7.kuroro.user
?????文件???????2560??2009-10-24?18:26??最近點對問題\test1.suo
?????文件??????41984??2009-10-29?18:00??最近點對問題\test1.ncb
?????文件???????3389??2009-10-29?17:42??最近點對問題\test1.dsp
?????文件???????4436??2009-10-29?17:56??最近點對問題\test1.cpp
?????文件??????48640??2009-10-29?18:00??最近點對問題\test1.opt
?????文件????????518??2009-10-29?18:00??最近點對問題\test1.dsw
?????目錄??????????0??2009-10-24?17:27??最近點對問題\Debug
?????目錄??????????0??2009-10-24?17:27??最近點對問題
-----------?---------??----------?-----??----
??????????????5186397????????????????????18
評論
共有 條評論