首页 > 代码库 > 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 ;}
HDU 3932
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。