|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
#include<iostream>
using namespace std;
struct POINT {
double x;
double y;
};
double DISTANCE(POINT a, POINT b);
double CLOSEST(POINT s[], int low, int high);
double FIND_MINIMUM(double d1, double d2, double d3);
int QUICKSORT(struct POINT p[],int begin,int end) ;
int PARTITION(POINT p, int begin, int end);
int main() {
POINT p[10]; //设定点的集合
int n;
cout << "输入点的个数:\n"; //输入点的个数
cin >> n;
cout << "输入点集:(x,y)\n";
for (int i = 0; i < n; i++)
cin >> p[i].x >> p[i].y;
double d=CLOSEST(p, 0,n); //对输入的点先排序
cout << "最小距离为:\n" << d; //输出点对的最小问题
return 0;
}
double DISTANCE(POINT a, POINT b) {
return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}
double FIND_MINIMUM(double d1,double d2) {
if (d1 < d2) {
return d1;
}
else if (d2 < d1)
{
return d2;
}
return 0;
}
double FIND_MINIMUM(double d1, double d2, double d3){
if ((d1 < d2) && (d1 < d3)) {
return d1;
}
else if ((d2 < d1) && (d2 < d3))
{
return d2;
}
else if ((d3 < d1) && (d3 < d2)) {
return d3;
}
return 0;
}
double CLOSEST(POINT s[] ,int low , int high ) {
double d1;
double d2;
double d3;
double d;
POINT *p=new POINT();
if (high - low == 1) {
return DISTANCE(s[low], s[high]);
}
if (high - low == 2) {
d1 = DISTANCE(s[low],s[low+1]);
d2 = DISTANCE(s[low + 1],s[high]);
d3 = DISTANCE(s[low],s[high]);
return FIND_MINIMUM(d1,d2,d3);
}
int middle = (low + high) / 2;
d1 = CLOSEST(s, low, middle);
d2 = CLOSEST(s, middle + 1, high);
d = FIND_MINIMUM(d1,d2);
int index = 0;
for (int i = middle; (i >= low) && (s[i].x >= s[middle].x - d); i--) {
p[index++] = s[i];
}
for (int j = middle + 1; (j <= high) && (s[j]).x <= s[middle].x + d; j++) {
p[index++] = s[j];
}
QUICKSORT(p,0,index-1);
for (int i = 0; i < index; i++) {
for (int j = i + 1; j < index; j++) {
if (p[j].y - p[i].y >= d) {
break;
}
else {
d3 = DISTANCE(p[i],p[j]);
if (d3 < d) { d = d3; }
}
}
}
return d;
}
int QUICKSORT(POINT p[], int begin, int end) {
if (begin < end) {
int sign = PARTITION(*p, begin, end);
PARTITION(*p,begin,sign-1);
PARTITION(*p,sign+1,end);
}
return 0;
}
int PARTITION(POINT p[], int begin, int end) {
double sign_element = p[end].y;
int i = begin - 1;
for (int j = begin; j < end; j++) {
if (p[j].y <= sign_element) {
i++;
exchange(p[i],p[j]);
}
}
exchange(p[i++], p[end]);
return i;
} |
|