【NOIP2018模拟赛2018.10.17】刺客信条(AC)
题目
题解
–这道题可以用二分,或者是并查集
但是怎么写check()是个大问题
首先,你可以发现,对于一个人,他能控制的范围是个圆
如果不能到终点的情况就是一串圆相连,把起点和终点隔开
所以可以用并查集维护连通性
当边界刚好联通的那个就是最远的距离
代码
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=2005;
int x,y,n;
int a[MAXN],b[MAXN];
struct hehe{
int u,v;
long long l;
}edge[MAXN*MAXN];
int cnt;
int f[MAXN];
long long ans;
void add_1(int i){
cnt++;
edge[cnt].u=i;
edge[cnt].v=n+1;
edge[cnt].l=1ll*min(a[i],y-b[i])*2;
edge[cnt].l*=edge[cnt].l;
cnt++;
edge[cnt].u=i;
edge[cnt].v=n+2;
edge[cnt].l=1ll*min(x-a[i],b[i])*2;
edge[cnt].l*=edge[cnt].l;
}
void add_2(int i,int j){
cnt++;
edge[cnt].u=i;
edge[cnt].v=j;
edge[cnt].l=1ll*(a[i]-a[j])*(a[i]-a[j])+1ll*(b[i]-b[j])*(b[i]-b[j]);
}
bool comp(const hehe &a,const hehe &b){
return a.l<b.l;
}
int get(int x){
if(x==f[x])
return x;
return f[x]=get(f[x]);
}
int main(){
cin>>x>>y>>n;
for(int i=1;i<=n;i++)
scanf("%d%d",&a[i],&b[i]);
for(int i=1;i<=n;i++){
add_1(i);
for(int j=1;j<i;j++)
add_2(i,j);
}
sort(edge+1,edge+1+cnt,comp);
for(int i=1;i<=n+2;i++)
f[i]=i;
for(int i=1;i<=cnt;i++){
int fu=get(edge[i].u);
int fv=get(edge[i].v);
if(fu==fv)
continue;
f[fu]=fv;
ans=max(ans,edge[i].l);
if(get(n+1)==get(n+2))
break;
}
printf("%.2lf",(double)sqrt(ans)/2);
return 0;
}