AOJ 2478: Trading Ship

古いJAGの問題はAOJ-ICPCにも載っていないから、隠れた良問みたいなものもある。ということで記事にする。

長方形の下から上にてきと～なルートで行きたい。障害物がN個長方形の中にある。経路中でのこれらとの距離の最小値を最大化せよ。

解法
二分探索する。障害物を中心として半径Mの円を考えて、これを伝って左から右まで繋がっているなら下から上に行くことはできない。そうでなかったら行ける。
へやわけとかでよく使うテク。

#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<queue>
using namespace std;
double x[510];
double y[510];
int bfs[510];
double ABS(double a){return max(a,-a);}
double z[510];
int main(){
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	for(int i=0;i<c;i++){
		scanf("%lf%lf",x+i,y+i);
		z[i]=x[i];
	}
	std::sort(z,z+c);
	double dis=0;
	for(int i=0;i<c-1;i++)dis=max(dis,ABS(z[i]-z[i+1]));
	//printf("%.12f\n",dis);
	double left=0;
	double right=1100000000;
	for(int i=0;i<100;i++){
		double M=(left+right)/2;
		for(int j=0;j<c;j++)bfs[j]=0;
		queue<int>Q;
		for(int j=0;j<c;j++){
			if(x[j]<M){
				bfs[j]=1;
				Q.push(j);
			}
		}
		while(Q.size()){
			int at=Q.front();Q.pop();
			for(int j=0;j<c;j++){
				if(bfs[j])continue;
				if((x[j]-x[at])*(x[j]-x[at])+(y[j]-y[at])*(y[j]-y[at])<4*M*M){
					bfs[j]=1;
					Q.push(j);
				}
			}
		}
		bool dame=false;
		for(int j=0;j<c;j++){
			if(bfs[j]&&x[j]>(double)a-M){
				dame=true;
			}
		}
		if(dame)right=M;
		else left=M;
	}
	printf("%.12f\n",left);
}