「一本通1.2練習2」拡散(二分+検索)
10064 ワード
かくさん
次はテーマ転送ドアの問題解は1つの2点で、1つの時間を列挙するごとに今が1つのブロックにつながっていると判断します:つながったばかりで、まだとっくにつながっています;まだつながっていない.コードは次のとおりです.
次はテーマ転送ドアの問題解は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;
}