记录编号	106779	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[Ural 1520] 帝国反击战	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.842 s
提交时间	2014-06-19 10:16:57	内存使用	0.33 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define sqr(x) (x)*(x)
const int SIZEN=310;
const double INF=1e10,pi=acos(-1.0),eps=1e-8;
class POINT{
public:
	double x,y;
	double d;
};
int random(int x,int y){
	return rand()%(y-x+1)+x;
}
int N;
double R;
double ans=0.0;
POINT factory[SIZEN];//工厂
POINT P[SIZEN];
POINT O;
double distsqr(POINT a,POINT b){
	return sqr(a.x-b.x)+sqr(a.y-b.y);
}
double dist(POINT a,POINT b){
	return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y));
}
double calc(POINT a){//这里计算距离的平方
	if(distsqr(a,O)>R*R+eps) return -INF;//这一点必须用eps,因为合法的点很有可能在圆周上!
	double ans=INF;
	for(int i=1;i<=N;i++) ans=min(ans,distsqr(a,factory[i]));
	return ans;
}
void deal_radius(void){//圆心与某个点连线和圆的交点
	for(int i=1;i<=N;i++){
		double dr=dist(factory[i],O);
		if(dr<eps) continue;
		POINT a=factory[i];
		a.x=a.x*R/dr,a.y=a.y*R/dr;
		ans=max(ans,calc(a));
		a.x*=-1.0,a.y*=-1.0;
		ans=max(ans,calc(a));
	}
}
void deal_mid(void){//两点中垂线与圆的交点
	for(int i=1;i<=N;i++){
		for(int j=i+1;j<=N;j++){
			if(dist(factory[i],factory[j])<eps) continue;
			if(fabs(factory[i].y-factory[j].y)<eps){//中垂线是竖直的
				double x0=(factory[i].x+factory[j].x)/2.0,y0=sqrt(sqr(R)-sqr(x0));
				ans=max(ans,calc((POINT){x0,y0,0}));
				ans=max(ans,calc((POINT){x0,-y0,0}));
			}
			else{//用点斜式表示中垂线
				double k1=(factory[j].x-factory[i].x)/(factory[i].y-factory[j].y);
				double b1=((factory[j].y+factory[i].y)-k1*(factory[j].x+factory[i].x))/2.0;
				//x^2+(k1x+b1)^2=R^2
				double a=1.0+sqr(k1),b=2.0*k1*b1,c=sqr(b1)-sqr(R);
				//ax^2+bx+c=0
				double x1=(-b+sqrt(sqr(b)-4.0*a*c))/(a*2.0),x2=(-b-sqrt(sqr(b)-4.0*a*c))/(a*2.0);
				double y1=k1*x1+b1,y2=k1*x2+b1;
				ans=max(ans,calc((POINT){x1,y1,0}));
				ans=max(ans,calc((POINT){x2,y2,0}));
			}
		}
	}
}
void special_deal(void){
	deal_radius();
	deal_mid();
}
void jump(POINT &a,double r){//点为a,步长为r
	double alpha=random(0,359)/180.0*pi;
	POINT b;
	b.x=a.x+r*cos(alpha),b.y=a.y+r*sin(alpha);//圆上随便找个点
	b.d=calc(b);
	if(b.d>a.d) a=b;
	//事实证明只接受最优解更好,这酸爽简直不敢相信
}
void SA(void){
	int n=20;
	double delta=2.0*R/sqrt(n+0.0);
	int rep=30;
	for(int i=1;i<=n;i++){//随机
		double alpha=random(0,359)/180.0*pi;
		double r=random(0,R);
		P[i].x=cos(alpha)*r;
		P[i].y=sin(alpha)*r;
	}
	while(delta>1e-9){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=rep;j++) jump(P[i],delta);
		}
		delta*=0.9;//,T*=0.9;
	}
	for(int i=1;i<=n;i++) ans=max(ans,P[i].d);
}
void shuffle(void){
	for(int i=1;i<=N;i++) swap(P[i],P[random(i,N)]);
}
void read(void){
	O.x=O.y=0;
	scanf("%d%lf",&N,&R);
	for(int i=1;i<=N;i++) scanf("%lf%lf",&factory[i].x,&factory[i].y);
}
int main(){
	freopen("empirestrikesback.in","r",stdin);
	freopen("empirestrikesback.out","w",stdout);
	srand(time(0));
	read();
	shuffle();
	SA();
	special_deal();
	printf("%.8lf\n",sqrt(ans));
	return 0;
}