UVA 10245(The Closest Pair Problem)分治
程序员文章站
2022-06-06 20:38:24
...
题意:输入n个点,任意取两个点,求解最短距离……如果最短距离大于10000,输出"INFINITY"
思路:首先想到的是暴力……看来我是“暴力狂”啊!,因为点比较多,可能会超时……
先将点按照x或y排序(之前按照x和y排序,udebug上一些样例过不了,按照其中一个排序就过了…… 神奇!)
分治,每次将点分成左右两,由于个区间,求解两个区间中的距离最小值。但是两个区间的点没法求距离,因此用两个for循环求解两个区间之间的距离最小值。
#include<bits/stdc++.h>
#define LL long long
using namespace std;
struct Point
{
double x,y;
}p[10010];
double dis(Point p1,Point p2)
{
return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
double ans;
bool cmp(Point p1,Point p2)
{
return p1.y<p2.y;
}
void solve(int l,int r)
{
if(r<=l)
return ;
if(r-l==1)
{
ans=min(ans,dis(p[l],p[r]));
return ;
}
sort(p+l,p+r+1,cmp);
solve(l,(l+r)/2);
//solve((l+r)/2,(l+r)/2+1);
for(int i=l;i<=(l+r)/2;i++)
{
for(int j=(l+r)/2+1;j<=r;j++)
{
ans=min(ans,dis(p[i],p[j]));
}
}
solve((l+r)/2+1,r);
}
int main()
{
int n;
while(cin>>n&&n)
{
ans=40000;
for(int i=1;i<=n;i++)
{
cin>>p[i].x>>p[i].y;
}
sort(p+1,p+n+1,cmp);
solve(1,n);
if(ans-10000>1e-7)
{
cout<<"INFINITY"<<endl;
}
else
printf("%.4f\n",ans);
}
return 0;
}
上一篇: 二叉堆及堆排序JAVA实现原理详解
下一篇: 线性表双链表实现