[luogu] P2498 [SDOI2012]拯救小云公主 二分答案+bfs

前言

以为二分的是人到BOOS的距离 没想到可以直接二分BOOS的攻击距离 传送门 :

思路

BFS待研究

CODE

typedef pair pii;
map mp;

int cal(int x1,int y1,int x2,int y2){
	return pow(x1-x2,2)+ pow(y1-y2,2);
}

bool check(int d,double r){
	return r * r * 4 >d;
}

const int N  =  3e3+10;
const double eps = 1e-5;
int n,line,row;
int x[N],y[N];
int dist[N][N];
int st[N];
queue q;


bool bfs(double r){
	memset(st,0,sizeof st);
	while(!q.empty()) q.pop();

	for(int i=1;irow;
	line -- ,row -- ;
	for(int  i = 1;i>x[i]>>y[i];x[i]--,y[i] -- ;
	}

	for(int i=1;i