#C. 封闭计划

    传统题 文件IO:fence 1000ms 256MiB

封闭计划

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

某社交网络上有 NN 个人,编号为 1N1 \ldots N2N1052 \leq N \leq 10^5),拥有一种围绕 “某网”,一些仅在组内互相交流却不与其他组进行交流的兴趣小组,组成的复杂的社交网络。

每个人位于一张二维地图上的不同位置 (x,y)(x,y) ,并且我们知道有 MM 对朋友(1M<1051 \leq M<10^5)会相互联系。两个相互联系的人属于同一 “某网”。

为了升级网络系统,管理员想要建造一个四边与 xx 轴和 yy 轴平行的长方形封闭区域。管理员想要使得至少一个 “某网” 完全被封闭区所包围(在长方形边界上的人计为被包围的)。请帮助管理员求出满足他的要求的封闭区域的最小可能周长。有可能出现这一封闭区宽为 00 或高为 00 的情况。

输入文件 fence.in

输入的第一行包含 NNMM 。以下 NN 行每行包含一个人的 xx 坐标和 yy 坐标(至多 10810^8 的非负整数)。以下 MM 行每行包含两个整数 aabb ,表示 aabb 之间有联系。每个人都至少存在一个 “某网” 关系,并且输入中不会出现重复的 “某网” 关系。

输出文件 fence.out

输出满足管理员的要求的封闭区域的最小周长。

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
10

样例 2 见附加文件。

2024 复赛集训模拟赛(四)

未参加
状态
已结束
规则
OI
题目
4
开始于
2024-10-14 19:00
结束于
2024-10-17 19:00
持续时间
3.5 小时
主持人
参赛人数
4