洛谷SP34 RUNAWAY - Run Away

题意翻译
在给定范围内找一个点,使得距离所有点的最小值最大。
模拟退火

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#define int long long 
using namespace std;
const int N=10005;
int t,n,x,y;
double ansx,ansy; 
struct node{
   
	int x,y;	
}dian[N],zhn;
inline int read(){
   
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
   if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){
   x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
double cal(double now_x,double now_y){
   
	double maxx=2147483640.00;
	for(int i=1;i<=n;i++){
   
		double detx=(double)(dian[i].x)-now_x;
		double dety=(double)(dian[i].y)-now_y;
		double dis=sqrt(detx*detx+dety*dety);
		maxx=min(dis,maxx);
	}
	return maxx;
}
void SA(){
   
	double xx=ansx,yy=ansy;
	double ans=0.00;
	double b=2000.00,e=1e-14;
	double ch=0.993;
	for(double i=b;i>e;i*=ch){
   
		double new_x =xx+((rand()<<1)-RAND_MAX)*i;
        double new_y =yy+((rand()<<1)-RAND_MAX)*i;
        if(new_x>x||new_x<0||new_y>y||new_y<0) continue;
        double lgr=cal(new_x,new_y);
        if(lgr>ans){
   
        	ans=lgr;
        	xx=new_x;
        	yy=new_y;
        	ansx=xx;
        	ansy=yy;
		}
		else if((exp((lgr-ans)/i)*RAND_MAX)>rand()) {
   
			xx=new_x;
			yy=new_y;
		}
	}
}
main(){
   
    t=read();
    srand(23333333);
    srand(rand());
    srand(rand());//玄学种子
    while(t--){
   
    	int sum_x=0;
    	int sum_y=0;
    	x=read();y=read();n=read();
    	for(int i=1;i<=n;i++) {
   
    		dian[i].x=read();
    		dian[i].y=read();
    		sum_x+=dian[i].x;
    		sum_y+=dian[i].y;
		}
		ansx=(double)(sum_x)/n;
		ansy=(double)(sum_y)/n;
        SA();SA();SA();
        printf("The safest point is (%.1lf, %.1lf).\n", ansx, ansy);  
	}
	return 0;
} 

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-22 18:27
天津大学_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议