https://codeforces.com/group/5yyKg9gx7m/contest/269908/problem/A
题目描述：
给出每个牛的坐标。互相认识的牛形成一个圈子。用一个平行于x轴和y轴的矩形，把至少一个圈子圈住。问矩形周长最少为多少。
每个圈子有一个代表，就是并查集中的根，只要在他的圈子里，用和他一个圈子的更新最大最小即可。
代码：
#include <stdio.h> #include <cstring> #include <algorithm> #include <queue> #include <cmath> #include <iostream> using namespace std; const int maxn=1e5+6; int fa[maxn]; struct po { int y,x; }p[maxn]; struct mp { int maxy,maxx; int minx,miny; mp() { minx=99999999;miny=99999999; maxy=0;maxx=0; } }mi[maxn]; int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); } void Union(int x,int y) { int xr=find(x); int yr=find(y); fa[xr]=yr; } int main() { int n,m; cin>>n>>m; for(int i=1;i<=n;i++) { fa[i]=i; cin>>p[i].y; cin>>p[i].x; } for(int i=0;i<m;i++) { int a,b; cin>>a>>b; Union(a,b); } for(int i=1;i<=n;i++) { int f=find(i); mi[f].maxx=max(mi[f].maxx,p[i].x); mi[f].minx=min(mi[f].minx,p[i].x); mi[f].maxy=max(mi[f].maxy,p[i].y); mi[f].miny=min(mi[f].miny,p[i].y); } int ans=999999999; for(int i=1;i<=n;i++) { int f=find(i); ans=min(ans,(mi[f].maxy-mi[f].miny+mi[f].maxx-mi[f].minx)*2); } cout<<ans<<endl; return 0; }
原文：https://www.cnblogs.com/studyshare777/p/12353954.html