首页 > 代码库 > HDU 1109
HDU 1109
http://acm.hdu.edu.cn/showproblem.php?pid=1109
一个范围内给一堆点,求到这些点的最短距离最大
模拟退火,温度是步长
#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(){ int T ; scanf("%d",&T) ; srand(time(NULL)) ; while(T--) { 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<50 ;i++) { r[i].x=(rand()%1000+1)/1000.0*X ; r[i].y=(rand()%1000+1)/1000.0*Y ; ans[i]=1e18 ; for(int j=0 ;j<M ;j++) { ans[i]=min(ans[i],dis(p[j],r[i])) ; } } double tmp=max(X,Y) ; while(tmp>0.01) { for(int i=0 ;i<50 ;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=1e18 ; for(int k=0 ;k<M ;k++) m=min(m,dis(p[k],next)) ; if(m>ans[i]) { ans[i]=m ; r[i]=next ; } } } tmp*=0.8 ; } double res=0.0 ; int idx ; for(int i=0 ;i<50 ;i++) { if(ans[i]>res) { res=ans[i] ; idx=i ; } } printf("The safest point is (%.1lf, %.1lf).\n",r[idx].x,r[idx].y) ; } return 0 ;}
HDU 1109
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。