首页 > 代码库 > HDU 3932

HDU 3932

http://acm.hdu.edu.cn/showproblem.php?pid=3932

一定范围的平面上给一些点,求到这些点的最大距离最小,和上一题的题意正好相反,稍微改一下就可以

这个问题又叫最小圆覆盖

#include <iostream>#include <cstdio>#include <cstring>#include <map>#include <ctime>#include <cmath>using namespace std ;const double eps=1e-18 ;int X,Y,M ;struct point{    double x,y ;    int OK()    {        if(x>-eps && x<X+eps && y>-eps && y<Y+eps)return 1 ;        return 0 ;    }}p[1005],r[50] ;double dis(point a,point b){    return sqrt(pow(a.x-b.x,2)+pow(b.y-a.y,2)) ;}double ans[55] ;int main(){    srand(time(NULL)) ;    while(~scanf("%d%d%d",&X,&Y,&M))    {        for(int i=0 ;i<M ;i++)        {            scanf("%lf%lf",&p[i].x,&p[i].y) ;        }        for(int i=0 ;i<20 ;i++)        {            r[i].x=(rand()%1000+1)/1000.0*X ;            r[i].y=(rand()%1000+1)/1000.0*Y ;            ans[i]=0.0 ;            for(int j=0 ;j<M ;j++)            {                ans[i]=max(ans[i],dis(p[j],r[i])) ;            }        }        double tmp=max(X,Y) ;        while(tmp>0.01)        {            for(int i=0 ;i<20 ;i++)            {                point now=r[i],next ;                for(int j=0 ;j<50 ;j++)                {                    double rad=(rand()%1000+1)/1000.0*2*3.1415926535 ;                    next.x=now.x+cos(rad)*tmp ;                    next.y=now.y+sin(rad)*tmp ;                    if(!next.OK())continue ;                    double m=0.0 ;                    for(int k=0 ;k<M ;k++)                        m=max(m,dis(p[k],next)) ;                    if(m<ans[i])                    {                        ans[i]=m ;                        r[i]=next ;                    }                }            }            tmp*=0.8 ;        }        double res=1e18 ;        int idx ;        for(int i=0 ;i<20 ;i++)        {            if(ans[i]<res)            {                res=ans[i] ;                idx=i ;            }        }        printf("(%.1lf,%.1lf).\n%.1lf\n",r[idx].x,r[idx].y,res) ;    }    return 0 ;}
View Code

 

HDU 3932