【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;
}