「一本通1.2練習2」拡散(二分+検索)

10064 ワード

かくさん
次はテーマ転送ドアの問題解は1つの2点で、1つの時間を列挙するごとに今が1つのブロックにつながっていると判断します:つながったばかりで、まだとっくにつながっています;まだつながっていない.コードは次のとおりです.
#include 
using namespace std;
int n,l,mid,r=2147483647,a[10005],b[10005],c[10005],k,ans;
int g(int x){
	return x==c[x]?c[x]:c[x]=g(c[x]); 
}
int f(int x){
    k=0;
    for (int i=1;i<=n;i++){
    	c[i]=i;
	}
    for (int i=1;i<=n;i++){
    	for (int j=i+1;j<=n;j++){
    		if (abs(a[i]-a[j])+abs(b[i]-b[j])<=x*2){
    			c[g(j)]=g(i);
			}
		}
	}
    for (int i=1;i<=n;i++){
    	if (c[i]==i){
    		k++;
		}
	}
    return k==1;
}
int main(){
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
    	scanf("%d%d",&a[i],&b[i]);
    }
    while (l<=r){
        mid=(l+r)>>1;
        if (f(mid)){
        	ans=mid;
			r=mid-1;
		}else{
        	l=mid+1;
		}
    }
    printf("%d",ans);
    return 0;
}