RecordIDError提交不了,有没有好心人帮忙交一下
查看原帖
RecordIDError提交不了,有没有好心人帮忙交一下
744789
Big_Bishop楼主2023/10/25 16:43
#include<cstdio>
#include<algorithm>
#include<random>
#include<ctime>
#include<cmath>
using namespace std;
mt19937 myrand(time(NULL));
int read(){
	int p=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') p=(p<<1)+(p<<3)+ch-'0',ch=getchar();
	return p;
}
double dis(double x1,double y1,double x2,double y2){
	return sqrt(1.0*(x1-x2)*(x1-x2)+1.0*(y1-y2)*(y1-y2));
}

const int N=1005;
int _,x,y,n;
int a[N],b[N];
double check(double x1,double y4){
	double sum=1e9;
	for(int i=1;i<=n;i++){
		sum=min(sum,dis(x1,y4,a[i],b[i]));
	}
	return sum;
}
double qu(double l,double r){
	return l+myrand()%int(r-l+1);
}
double p,q,sum;
void pa(){
	double chux=qu(0.0,x*1.0),chuy=qu(0.0,y*1.0);
	double hua1=check(chux,chuy);
	for(double t=100000;t>=1e-7;t*=0.997){
		if(chux-t<0||chux+t>x||chuy-t<0||chuy+t>y) continue;
		double ansx=qu(max(0.0,chux-t),min(x*1.0,chux+t));
		double ansy=qu(max(0.0,chuy-t),min(y*1.0,chuy+t));
		double hua=check(ansx,ansy);
		if(hua>hua1){
			chux=ansx,chuy=ansy;
			hua1=hua;
		}
		if(hua1>sum){
			sum=hua1;
			p=chux,q=chuy;
		}
	}
}
int main(){
	_=read();
	while(_--){
		x=read(),y=read(),n=read();
		for(int i=1;i<=n;i++) a[i]=read(),b[i]=read();
		p=x/2,q=y/2;
		sum=check(p,q);
//		printf("%.1lf %.1lf\n",p,q);
		int __=100;
		while(__--){
			pa();
		}	
		printf("The safest point is (%.1lf, %.1lf).\n",p,q);
	}
	return 0;
}
2023/10/25 16:43
加载中...