记录编号	422623	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[Ural 1520] 帝国反击战	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	3.653 s
提交时间	2017-07-10 08:09:24	内存使用	2.58 MiB

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<climits>
using namespace std;
typedef long double db;
const int N=1e5+10;
const db pi=acos(-1.0);
db sqr(db x){return x*x;}
int n,r;
struct pt{
	db x,y;
	pt(db X=0,db Y=0){x=X;y=Y;}
	pt operator - (const pt a)const{return pt(x-a.x,y-a.y);}
	db len(){return sqr(x)+sqr(y);}
}p[N],ansp;
db ans;
db distance(pt x){
	db Min=1e9;
	for (int i=1;i<=n;i++) Min=min(Min,(p[i]-x).len());
	if (Min>ans) ans=Min,ansp=x;
	return Min;
}
const db step=pi/40;
void solve(pt now){//爬山法
	if (clock()>650000) return;
	db R=r*0.1;//当前步长
	db C=0.93;//缩减速度
	db eps=1e-10;//精度
	db now_val=distance(now);
	int cnt=381;
	for (;R>eps;R*=C){
		//printf("(%.5Lf,%.5Lf)\n",now.x,now.y);
		pt last=now;
		for (db alpha=0;alpha<pi*2;alpha+=step){
			pt next(last.x+R*sin(alpha),last.y+R*cos(alpha));
			if (next.len()>r*r+2e-5) continue;
			db next_val=distance(next);
			if (next_val>now_val) now_val=next_val,now=next;
		}
		cnt--;
		if (cnt*R+sqrt(now_val)<sqrt(ans)) return;
	}
}
int rand(int n){return rand()%n+1;}
db _rand(){return 1.0*rand()/INT_MAX;}
int main()
{
	//freopen("a.txt","r",stdin);
	freopen("empirestrikesback.in","r",stdin);
	freopen("empirestrikesback.out","w",stdout);
	srand(time(0));
	scanf("%d%d",&n,&r);
	for (int i=1;i<=n;i++) scanf("%Lf%Lf",&p[i].x,&p[i].y);
	db R,step;
	R=r*1.0/3.0,step=pi/3;
	for (db alpha=0;alpha<pi*2;alpha+=step) solve(pt(R*cos(alpha),R*sin(alpha)));
	R=r*2.0/3.0,step=pi/6;
	for (db alpha=0;alpha<pi*2;alpha+=step) solve(pt(R*cos(alpha),R*sin(alpha)));
	for (int i=1;i<=20;i++){
		db R=_rand()*r,alpha=_rand()*pi*2;
		solve(pt(R*cos(alpha),R*sin(alpha)));
	}
	/*R=r*1.0/4.0,step=pi/6;
	for (db alpha=0;alpha<pi*2;alpha+=step) solve(pt(R*cos(alpha),R*sin(alpha)));
	R=r*2.0/4.0,step=pi/8;
	for (db alpha=0;alpha<pi*2;alpha+=step) solve(pt(R*cos(alpha),R*sin(alpha)));
	R=r*3.0/4.0,step=pi/10;
	for (db alpha=0;alpha<pi*2;alpha+=step) solve(pt(R*cos(alpha),R*sin(alpha)));
	for (int i=1;i<=30;i++){
		db R=_rand()*r,alpha=_rand()*pi*2;
		solve(pt(R*cos(alpha),R*sin(alpha)));
	}*/
	R=5e-6,step=pi/1000;
	for (db alpha=0;alpha<pi*2;alpha+=step){
		pt next(ansp.x+R*cos(alpha),ansp.x+R*sin(alpha));
		if (next.len()>r*r+2e-5) continue;
		distance(next);
	}
	printf("%.10Lf\n",sqrt(ans));
	return 0;
}