Pak Chanek有n个二维奶酪片。第i片奶酪可以表示为一个尺寸为ai×bi的矩形。我们想把它们安排在二维平面上，这样。
每块奶酪的每条边都平行于X轴或Y轴。
每块奶酪的底边是x轴的一段。
没有两片奶酪重叠，但它们的边可以接触。
它们形成一个相连的形状。
请注意，我们可以以任何顺序排列它们（最左边的那片奶酪不一定是第一片奶酪）。还要注意的是，我们可以以任何方式旋转每片奶酪，只要所有的条件仍然成立。
找出所建图形的最小可能周长。
2733: 巨无霸特级奶酪
时间限制: 1 Sec 内存限制: 128 MB提交: 0 解决: 26
[提交][状态][讨论版][命题人:]
题目描述
输入描述
每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤2⋅104）--测试用例的数量。下面几行包含每个测试用例的描述。
每个测试用例的第一行包含一个整数n (1≤n≤2⋅109)--Pak Chanek的奶酪片的数量。
每个测试案例接下来的n行中的第i行包含两个整数ai和bi（1≤ai,bi≤1010）--第i片奶酪的尺寸。
可以保证所有测试用例的n之和不超过2⋅105。
每个测试用例的第一行包含一个整数n (1≤n≤2⋅109)--Pak Chanek的奶酪片的数量。
每个测试案例接下来的n行中的第i行包含两个整数ai和bi（1≤ai,bi≤1010）--第i片奶酪的尺寸。
可以保证所有测试用例的n之和不超过2⋅105。
输出描述
对于每个测试案例，输出一条包含整数的值，代表构建的形状的最小可能周长。
样例输入
3
4
4 1
4 5
1 1
2 3
3
2 4
2 6
2 3
1
2 65
样例输出
26
24
134
提示
在第一个测试用例中，获得最小周长的一种方法是按如下方式排列奶酪片。
我们可以计算出构造形状的周长为2+5+1+1+1+1+1+3+1+5+1+2+3=26可以证明，我们不能得到更小的周长。
请考虑以下无效安排。
即使上面形状的周长是24，它不满足问题的所有条件。底部边缘1 x 1奶酪片不是 X轴的一部分。
在第二个测试用例中，获得最小周长的一种方法是按如下方式排列奶酪片。
我们可以计算出构造形状的周长为2+2+2+3+2+3+2+2+2+4=24.可以证明，我们不能得到更小的周长。
来源
-
Anything about this OnlineJudge, Please Contact Administrator. Click add QQ
OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap
Copyright 2016 ACM算法攻关部
关于网站改版