1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
| //
// main.cpp
// 算法设计作业
//
// Created by Elli0t on 2020/10/25.
//
#include <iostream>
#include <math.h>
/*
int main(int argc, const char * argv[]) {
// insert code here...
std::cout << "test";
return 0;
}
*/
using namespace std;
double ClosestPoints(int x[], int y[], int length) {
double MAX_DISTANCE = 0;
if (length == 1){
cout<< "请输入两个或者两个以上点" << endl;
return MAX_DISTANCE;
}
else if (length == 2){
MAX_DISTANCE = pow(pow(x[0] - x[1], 2) + pow(y[0]-y[1], 2), 0.5); // 两个点的情况
cout<< "最近的两个点是: 0 1" << endl;
return MAX_DISTANCE;
}
else{
double mindis;
int minPoint_1[2], minPoint_2[2]; // 每个数组第一位储存 x , 第二位储存 y , 用的都是一维数组
minPoint_1[0] = x[0];
minPoint_1[1] = y[0];
minPoint_2[0] = x[1];
minPoint_2[1] = y[1];
mindis = pow(pow(x[0] - x[1], 2) + pow(y[0]-y[1], 2), 0.5);
int i = 0, j = 1;
double temp = 0;
for (i = 0; i < length - 1; i++) {
for (j = i + 1; j < length; j++) {
temp = pow(pow(x[i] - x[j], 2) + pow(y[i]-y[j], 2), 0.5);
if (temp < mindis) {
temp = mindis;
minPoint_1[0] = x[i];
minPoint_1[1] = y[i];
minPoint_2[0] = x[j];
minPoint_2[1] = y[j];
}
}
}
cout<< "最近的两个点分别是: (" << minPoint_1[0] << ", " << minPoint_1[1] << ") 和 (" << minPoint_2[0] << ", " << minPoint_2[1] << ")" << endl;
return temp;
}
}
//蛮力法
/*
double BruteForceMethod(Node p[], int length)
{
if (length == 1) //点数为1输出无穷大
return MAX_DISTANCE;
else if (length == 2) //点数为2直接输出点距
return ((p[0].x - p[1].x)*(p[0].x - p[1].x) + (p[0].y - p[1].y)*(p[0].y - p[1].y));
else{
int i, j;
double mindis, temp;
mindis = (p[0].x - p[1].x)*(p[0].x - p[1].x) + (p[0].y - p[1].y)*(p[0].y - p[1].y); //先取前两个点的点距为最小距离
minPoint1 = p[0];
minPoint2 = p[1];
for (i = 0; i < length - 1; i++){
for (j = i + 1; j < length; j++){
temp = (p[i].x - p[j].x)*(p[i].x - p[j].x) + (p[i].y - p[j].y)*(p[i].y - p[j].y); //算出每两个点的点距
if (temp < mindis){ {
mindis = temp; //当发现更小的距离时，替换最小点距，并记录两个点的信息
minPoint1 = p[i];
minPoint2 = p[j];
}
}
}
return mindis; //直到返回结果时才求sqrt得到真正距离，减少运算量
}
}
*/
int main(int argc, const char * argv[])
{
int n;
cout<<"请输入集合中点的个数（0-100):";
cin>>n;
int x[100];
int y[100];
cout<<"请输入集合中所有点的x坐标:"<<endl;
double res = 0;
for (int i=0; i<n; i++) cin>>x[i];
cout<<"请输入集合中所有点的y坐标:"<<endl;
for (int j=0; j<n; j++) cin>>y[j];
res = ClosestPoints( x, y, n);
cout<<"result: " << res << endl;
return 0;
}
|