?#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