您的位置:首页 > 国际新闻

Fence Planning//并查集

时间:2020-03-04

围栏规划//并查集

题目

农夫约翰的N头牛,方便地编号为1…N (2≤N≤105),有一个围绕“哞网络"的复杂的社会结构较小的奶牛群体在它们的群体内交流,但不与其他群体交流。在农场的2D地图上,每头奶牛都位于一个不同的位置,我们知道有M对奶牛(1≤M105)在互相哞哞叫。两头互相哞叫的牛属于同一个哞网络

为了更新他的农场,农夫约翰想建一个长方形的栅栏,它的边缘平行于x轴和y轴。农民约翰想确保至少有一个牛叫声网络被围栏完全封闭(矩形边界上的牛被视为被封闭).请帮助农民约翰确定满足这一要求的围栏的最小可能周长。这个栅栏有可能是零宽或零高

输入

输入的第一行包含N和m .接下来的N行分别包含奶牛的x和y坐标(大小不超过108的非负整数).接下来的M行各包含两个整数a和b、描述了牛a和牛b之间的牛叫声连接。每头牛至少有一个牛叫声连接,输入中没有重复连接

输出

请打印满足农民约翰要求的最小围栏周长

示例

InputCopy

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

OutputCopy

10

题意

给坐标,给出哪几个数之间有联系,用矩形框,至少框到一个组。求矩形最小面积

思路

利用并查集分好组,每一个同根的数求各边的最值,求出每一组的面积再比较

代码

注意

  • 友情链接:
  • 良庆农业网 版权所有© www.giltattoo.com 技术支持:良庆农业网| 网站地图