欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

UVA 10245(The Closest Pair Problem)分治

程序员文章站 2022-06-06 20:38:24
...

UVA 10245(The Closest Pair Problem)分治

题意:输入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;
}

相关标签: 分治