C++ 代码

//先画图分析
//然后基本思路是并查集，并查集的根节点维护一个矩形，用来表示框住当前并查集的这个块最小的矩形，每次动态更新。
//更新方式，先对于每个块存这个矩形的左上和右下两个点的位置，对于每条连边，用新加的块更新原有的块的四个坐标，然后把新加的块并到原有块的并查集里面
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=200050;
int p[N];
int find(int x){
    if(x==p[x]) return x;
    int root=find(p[x]);
    return p[x]=root;
}
struct Martix{                                   //矩阵，存左上和右下的坐标
    PII u,v;
}w[N];
int n,m;
PII points[N];                                    //点的坐标，点的编号从1开始
void uni(int a,int b){
    a=find(a);
    b=find(b);
    if(a==b) return;
    //修改a的值然后把b合并到a里
    w[a].u.x=min(w[a].u.x,w[b].u.x);
    w[a].u.y=min(w[a].u.y,w[b].u.y);
    w[a].v.x=max(w[a].v.x,w[b].v.x);
    w[a].v.y=max(w[a].v.y,w[b].v.y);
    p[b]=a;
}
int main(){

    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        points[i].x=a;
        points[i].y=b;
        p[i]=i;
        w[i].u={a,b};
        w[i].v={a,b};
    }

    while(m--){
        int a,b;
        scanf("%d%d",&a,&b);
        uni(a,b);
    }
    int res=0x3f3f3f3f;

    for(int i=1;i<=n;i++){
        if(p[i]==i){
            int a=w[i].v.y-w[i].u.y;
            int b=w[i].v.x-w[i].u.x;
            res=min(res,2*(a+b));
        }
    }

    cout<<res;

    return 0;

}