menu Home Tags Archives Video About
算法-最近点对问题(暴力破解法)

一言加载中...

通过暴力方式,进行一次比较获取两个点之间的最短距离,思路:

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
//点对最近问题(暴力破解法)

#include<iostream>
#include<cmath>
using namespace std;

double distance(double x1,double y1,double x2,double y2)
{
//返回两点之间的距离
return sqrt(pow((x1-x2),2)+pow((y1-y2),2));
}

int main()
{
int n;
cin>>n;
double a[n][2];

//init
for(int i=0;i<n;i++)
{
for(int j=0;j<2;j++)
{
cin>>a[i][j];
}
}

double length=distance(a[0][0],a[0][1],a[1][0],a[1][1]);
cout<<length<<endl;
//find
for(int i=0;i<n-1;i++)
{
for(int j=i+1;j<n;j++)
{
double temp=distance(a[i][0],a[i][1],a[j][0],a[j][1]);
if(temp<length)
{
length=temp;
}
}
}
cout<<length;
}

过于简单就不做过多的解释,如有问题欢迎私聊!
对于二分法寻找最近点距离,下次再写喽。

2017.10.17
Tony-Chen
Only forget the past ,The furture will not burdon!

评论