7467: Play osu! on Your Tablet
内存限制：128 MB
时间限制：5 S
标准输入输出
题目类型：传统
评测方式：文本比较
上传者：
提交：0
通过：0
题目描述
Little Q is an enthusiast of rhythm games, and recently he began to play osu! (standard mode) on his tablet.
In the game, his goal is to hit objects (circles, sliders, spinners, etc.) at the right time, and the more hits are perfectly timed, the more total score he gets. Additionally, since his tablet and this game support multi-finger control, he is able to play with two or more fingers. Here are a few snapshots of the game interface.
During his performance-enhancing play, he suddenly comes up with the following question:
There are several oncoming circles on the interface, whose perfect time to hit are pairwisely distinct, and Little Q wants to hit them at the right time using only two fingers. Besides, he wants to minimize the total cost of moving his fingers, where the cost of moving one finger between two circles is equal to the Manhattan distance between the centers of these two circles, and the total cost is the sum of costs for each finger.
Stunned by your excellent problem-solving capability, he would like to ask you to find the minimum total cost.
By the way, the Manhattan distance between two points (x![]()
0![]()
,y![]()
0![]()
)![]()
and (x![]()
1![]()
,y![]()
1![]()
)![]()
is defined as |x![]()
0![]()
−x![]()
1![]()
|+|y![]()
0![]()
−y![]()
1![]()
|![]()
, where |p|![]()
is the absolute value of p![]()
.
For more details about osu!, you may refer to http://osu.ppy.sh/help/wiki/Main_Page.
In the game, his goal is to hit objects (circles, sliders, spinners, etc.) at the right time, and the more hits are perfectly timed, the more total score he gets. Additionally, since his tablet and this game support multi-finger control, he is able to play with two or more fingers. Here are a few snapshots of the game interface.
During his performance-enhancing play, he suddenly comes up with the following question:
There are several oncoming circles on the interface, whose perfect time to hit are pairwisely distinct, and Little Q wants to hit them at the right time using only two fingers. Besides, he wants to minimize the total cost of moving his fingers, where the cost of moving one finger between two circles is equal to the Manhattan distance between the centers of these two circles, and the total cost is the sum of costs for each finger.
Stunned by your excellent problem-solving capability, he would like to ask you to find the minimum total cost.
By the way, the Manhattan distance between two points (x
For more details about osu!, you may refer to http://osu.ppy.sh/help/wiki/Main_Page.
输入格式
There are several test cases.
The first line contains an integer T![]()
(1≤T≤1000)![]()
, denoting the number of test cases. Then follow all the test cases.
For each test case, the first line contains an integer n![]()
(1≤n≤10![]()
5![]()
)![]()
, denoting the number of oncoming circles.
The next n![]()
lines describe these circles in chronological order of occurrence, where the i![]()
-th line contains two integers x![]()
i![]()
![]()
and y![]()
i![]()
![]()
(0≤x![]()
i![]()
,y![]()
i![]()
≤10![]()
9![]()
)![]()
, representing a circle with center (x![]()
i![]()
,y![]()
i![]()
)![]()
.
It is guaranteed that the sum of n![]()
in all test cases is no larger than 3×10![]()
5![]()
![]()
.
The first line contains an integer T
For each test case, the first line contains an integer n
The next n
It is guaranteed that the sum of n
输出格式
For each test case, output in one line the minimum total cost.
输入样例 复制
2
3
0 1
1 0
1 1
3
0 1
4 0
2 1
输出样例 复制
1
2