2020 GDUT Rating Contest II (Div. 2) A. Fence Planning

来源 codeforces 2020 GDUT Rating Contest II (Div. 2) CF链接

题目：
Farmer John’s N cows, conveniently numbered 1…N (2≤N≤1e5), have a complex social structure revolving around “moo networks” — smaller groups of cows that communicate within their group but not with other groups. Each cow is situated at a distinct (x,y) location on the 2D map of the farm, and we know that M pairs of cows (1≤M<1e5) moo at each-other. Two cows that moo at each-other belong to the same moo network.

In an effort to update his farm, Farmer John wants to build a rectangular fence, with its edges parallel to the x and y axes. Farmer John wants to make sure that at least one moo network is completely enclosed by the fence (cows on the boundary of the rectangle count as being enclosed). Please help Farmer John determine the smallest possible perimeter of a fence that satisfies this requirement. It is possible for this fence to have zero width or zero height.

Input
The first line of input contains N and M. The next N lines each contain the x and y coordinates of a cow (nonnegative integers of size at most 108). The next M lines each contain two integers a and b describing a moo connection between cows a and b. Every cow has at least one moo connection, and no connection is repeated in the input.

Output
Please print the smallest perimeter of a fence satisfying Farmer John’s requirements.

Example
input
7 5
0 5
10 5
5 0
5 10
6 7
8 6
8 4
1 2
2 3
3 4
5 6
7 6
output
10

题意：n头牛在不同的位置，某两头牛是一伙的，并且和一伙的其他牛的一伙的也是一伙的，求一最短的栅栏能把其中某一伙牛给框起来。
思路：用并查集来维护，每加入一头牛到这个集团就更新这个集团的四个角的坐标到集团首，然后枚举每个集团需要多长的栅栏即可。

代码:

#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> #define INF 0x3f3f3f3f #define mod 1000000007 using namespace std; struct cow {int a,b,c,d; }k[100010]; int n,m,pre[100010]; int find(int x) {int k=x;while (pre[x]!=x)x=pre[x];pre[k]=x;return x; } void join(int a,int b) {int x=find(a),y=find(b);if (x!=y){pre[x]=y;k[y].a=min(k[x].a,k[y].a);k[y].b=max(k[x].b,k[y].b);k[y].c=min(k[x].c,k[y].c);k[y].d=max(k[x].d,k[y].d);} } int main() {cin>>n>>m;for (int i=1;i<=n;i++){scanf("%d%d",&k[i].a,&k[i].c);k[i].b=k[i].a,k[i].d=k[i].c;}int a,b;for (int i=1;i<=n;i++) pre[i]=i;for (int i=1;i<=m;i++){scanf("%d%d",&a,&b);join(a,b);}long long ans=400000001;for (int i=1;i<=n;i++){long long L;int x=find(i);L=2*(k[x].b-k[x].a+k[x].d-k[x].c);ans=min(ans,L);}cout<<ans;return 0; }

总结

以上是生活随笔为你收集整理的2020 GDUT Rating Contest II (Div. 2) A. Fence Planning的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。