题意:给一系列坐标,然后让你求最近点对的1/2的距离!!!
思路:我一开始没怎么想,就暴力着把所有的点都遍历一遍,然后每次两个坐标得到一个距离,然后每次min得到最小的距离,所有的点遍历后就能得到最小距离。(超时!!!) 下面是错误代码,只考虑了相邻的两个点间的距离,我们必须要用两个for循环把所有的两两点遍历得到最小距离
#include<bits/stdc++.h>
#define maxn 100005
#define inf 0x3f3f3f3f
using namespace std;
int N;
struct node{
double x;
double y;
}a[maxn];
int main(){
while(cin>>N && N){
double minn = inf;
cin>>a[1].x>>a[1].y;
for(int i=2;i<=N;i++){
cin>>a[i].x>>a[i].y;
double r;
r = sqrt((a[i].x-a[i-1].x)*(a[i].x-a[i-1].x)+(a[i].y-a[i-1].y)*(a[i].y-a[i-1].y));
minn = min(minn,1.0/2.0 * r);
}
cout<<fixed<< setprecision(2)<<minn<<endl;
}
return 0;
}
然后我又想这个题不就是得到最小的两个坐标嘛,我就先把所有的坐标存入结构体坐标,然后的话我一个sort排序得到最近的两个坐标,我哭o(╥﹏╥)o了,菜是原罪。如果是负数的话,这个排序是错误的啊,负数的绝对值大的最后面,这个有可能就错失了真实的最短距离!!!垃圾!!我靠!!
#include<bits/stdc++.h>
#define maxn 100005
//#define inf 0x3f3f3f3f
using namespace std;
int N;
struct node{
double x;
double y;
}a[maxn];
int cmpp(node a,node b){
if(a.x = b.x) return a.y < b.y;
return a.x < a.y;
}
int main(){
while(cin>>N && N){
for(int i=0;i<N;i++){
cin>>a[i].x>>a[i].y;
}
sort(a,a+N,cmpp);
double ans = 1.0/2.0 *sqrt((a[1].x-a[0].x)*(a[1].x-a[0].x)+(a[1].y-a[0].y)*(a[1].y-a[0].y));
cout<<fixed<< setprecision(2)<<ans<<endl;
}
return 0;
}
暴力超时怎么办???!!!分治法来帮忙!!!
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 100005
struct node
{
double x,y;
} point[N];
int point1[N];//存储符合标准的点的坐标
bool cmpx(node a,node b)//按x坐标从小到大排序
{
return a.x<b.x;
}
bool cmpy(int a,int b)//按y坐标从小到大进行排序
{
return point[a].y<point[b].y;
}
double dist(node a,node b)//求出两点间的距离
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double near(int l,int r)//利用分治法找出最近的两个点的距离
{
if(l>=r)
return 1e10;
int mid=(l+r)/2;
int n=0;
double distan=min(near(l,mid),near(mid+1,r));//利用二分法分为两个区间
for(int i=mid; i>=l; --i)//把前一半符合条件的点的位置存入数组q中
{
if(point[mid].x-point[i].x<distan)
{
point1[n++]=i;
}
else break;
}
for(int i=mid+1; i<=r; ++i)//把后一半符合条件的点的位置存入数组q中
{
if(point[i].x-point[mid].x<distan)
{
point1[n++]=i;
}
else break;
}
sort(point1,point1+n,cmpy);//对这些点按纵坐标进行升序排序
for(int i=0; i<n; i++)
{
for(int j=i+1; j<n; j++)
{
if(point[point1[j]].y-point[point1[i]].y<distan)//找出这些点中距离的最小值
{
distan=min(dist(point[point1[i]],point[point1[j]]),distan);
}
else break;
}
}
return distan;
}
int main()
{
int n;
while(~scanf("%d",&n))
{
if(n==0)
break;
for(int i=0; i<n; i++)
{
scanf("%lf %lf",&point[i].x,&point[i].y);
}
sort(point,point+n,cmpx);
printf("%.2lf\n",near(0,n-1)/2);
}
return 0;
}