题意：河里有n块石头，一只青蛙要从左岸跳到右岸，你可以再在任意一个位置放一块石头，使得在最优方案下，青蛙单步跳的距离的最大值最小化，输出该位置。
将原图视作完全图，二分答案mid，然后在图中只保留小于等于mid的边，分别用dfs处理左岸能到哪些石头，右岸能到哪些石头。然后二重循环枚举两侧这些点对，如果存在一对点，它们的距离不超过2*mid，那么mid可行，将石头放在它们的中点即可。否则不可行。
要注意，左岸和右岸也需要当成点，不过距离计算时会稍微麻烦一点，需要讨论一下。
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
const double EPS=0.001;
struct Point{
ll x,y;
Point(const ll &x,const ll &y){
this->x=x;
this->y=y;
}
Point(){}
double length(){
return sqrt((double)x*(double)x+(double)y*(double)y);
}
void read(){
scanf("%lld%lld",&x,&y);
}
}p[1005];
typedef Point Vector;
Vector operator - (const Point &a,const Point &b){
return Vector(a.x-b.x,a.y-b.y);
}
int n,m;
double dis(int i,int j){
if(i==0 && j==0 || i==m+1 && j==m+1){
return 0.0;
}
if(i==0 && j==m+1 || i==m+1 && j==0){
return (double)n;
}
if(i==0){
return (double)p[j].x;
}
if(j==0){
return (double)p[i].x;
}
if(i==m+1){
return (double)(n-p[j].x);
}
if(j==m+1){
return (double)(n-p[i].x);
}
return (p[i]-p[j]).length();
}
double mid;
bool can[2][1005];
void dfs(int U){
can[0][U]=1;
for(int i=1;i<=m;++i){
if(!can[0][i] && dis(U,i)-mid<EPS){
dfs(i);
}
}
}
void df2(int U){
can[1][U]=1;
for(int i=1;i<=m;++i){
if(!can[1][i] && dis(U,i)-mid<EPS){
df2(i);
}
}
}
int main(){
freopen("froggy.in","r",stdin);
freopen("froggy.out","w",stdout);
scanf("%d%d",&n,&m);
if(m==0){
printf("%.3f %.3f
",(double)n*0.5,1.0);
return 0;
}
for(int i=1;i<=m;++i){
p[i].read();
}
double l=0.0,r=(double)n;
double anx,any;
while(r-l>EPS){
memset(can,0,sizeof(can));
mid=(l+r)*0.5;
dfs(0);
df2(m+1);
bool flag=0;
for(int i=0;i<=m+1;++i){
bool ok=0;
for(int j=0;j<=m+1;++j){
if(can[0][i] && can[1][j] && dis(i,j)-2.0*mid<EPS){
ok=1;
if(i==0 && j==m+1 || i==m+1 && j==0){
anx=(double)n*0.5;
any=1.0;
}
else if(i==0 && j==0){
continue;
}
else if(i==m+1 && j==m+1){
anx=(double)n;
any=0.0;
}
else if(i==0){
anx=(double)p[j].x*0.5;
any=(double)p[j].y;
}
else if(j==0){
anx=(double)p[i].x*0.5;
any=(double)p[i].y;
}
else if(i==m+1){
anx=(double)(p[j].x+n)*0.5;
any=(double)p[j].y;
}
else if(j==m+1){
anx=(double)(p[i].x+n)*0.5;
any=(double)p[i].y;
}
else{
anx=(double)(p[i].x+p[j].x)*0.5;
any=(double)(p[i].y+p[j].y)*0.5;
}
break;
}
}
if(ok){
flag=1;
break;
}
}
if(flag){
r=mid;
}
else{
l=mid+EPS;
}
}
printf("%.3f %.3f
",anx,any);
return 0;
}