Play osu! on Your Tablet
TimeLimit:5000MS MemoryLimit:524288KB
64-bit integer IO format:%I64d
未提交 | 登录后收藏
Problem Description
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_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.
Input
There are several test cases.
The first line contains an integer $T$ $(1 \leq T \leq 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 \leq n \leq 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 \leq x_i, y_i \leq 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 \times 10^5$.
The first line contains an integer $T$ $(1 \leq T \leq 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 \leq n \leq 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 \leq x_i, y_i \leq 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 \times 10^5$.
Output
For each test case, output in one line the minimum total cost.
SampleInput
2 3 0 1 1 0 1 1 3 0 1 4 0 2 1
SampleOutput
1 2