2 solutions

  • 2
    @ 2022-6-7 17:30:40

    并查集加二分

    #include<iostream>
    #include<cmath>
    using namespace std;
    
    int n,d[57][57],f[57];
    struct A{
    	int  x,y;
    }p[57];
    
    int juli(A n1,A n2){
    	return abs(n1.x-n2.x)+abs(n1.y-n2.y);
    }
    
    int find(int x){
    	if(x==f[x])return x;
    	else return f[x]=find(f[x]);
    }
    
    bool check(int  x){
    	for(int i=0;i<n;i++)f[i]=i;
    	for(int i=0;i<n;i++){
    		for(int j=i+1;j<n;j++){
    			if(d[i][j]<=x*2){
    				int fx=find(i),fy=find(j);
    				if(fx!=fy)f[fx]=fy;
    			}
    		}
    	}
    	int sum=0;
    	for(int i=0;i<n;i++){
    		if(f[i]==i)sum++;
    		if(sum>=2)return false ;
    	}
    	return true;
    }
    
    int search(int l,int r){
    	int mid;
    	while(l<=r){
    		mid=(l+r+1)>>1;
    		if(check(mid))r=mid-1;
    		else l=mid+1;
    	}
    	return l;
    }
    
    int main(){
    	cin>>n;
    	for(int i=0;i<n;i++){
    		cin>>p[i].x>>p[i].y;
    	}
    	for(int i=0;i<n;i++){
    		for(int j=0;j<n;j++){
    			d[i][j]=juli(p[i],p[j]);
    			d[j][i]=d[i][j];
    		}
    	}
    	int ans=search(0,500000000);
    	cout<<ans;
    	return 0;
    }
    

    详情移步https://dueyin.github.io/posts/kmp_and_-sort/

    Information

    ID
    169
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    6
    Tags
    # Submissions
    59
    Accepted
    17
    Uploaded By