[Solution] Traveling Salesman Problem solution codeforces

Traveling Salesman Problem solution codeforces – You are living on an infinite plane with the Cartesian coordinate system on it. In one move you can go to any of the four adjacent points (left, right, up, down).

Table of Contents

[Solution] Traveling Salesman Problem solution codeforces

More formally, if you are standing at the point (𝑥,𝑦)(x,y), you can:

  • go left, and move to (𝑥1,𝑦)(x−1,y), or
  • go right, and move to (𝑥+1,𝑦)(x+1,y), or
  • go up, and move to (𝑥,𝑦+1)(x,y+1), or
  • go down, and move to (𝑥,𝑦1)(x,y−1).

There are 𝑛n boxes on this plane. The 𝑖i-th box has coordinates (𝑥𝑖,𝑦𝑖)(xi,yi). It is guaranteed that the boxes are either on the 𝑥x-axis or the 𝑦y-axis. That is, either 𝑥𝑖=0xi=0 or 𝑦𝑖=0yi=0.

You can collect a box if you and the box are at the same point. Find the minimum number of moves you have to perform to collect all of these boxes if you have to start and finish at the point (0,0)(0,0).

[Solution] Traveling Salesman Problem solution codeforces

The first line contains a single integer 𝑡t (1𝑡1001≤t≤100) — the number of test cases.

The first line of each test case contains a single integer 𝑛n (1𝑛1001≤n≤100) — the number of boxes.

The 𝑖i-th line of the following 𝑛n lines contains two integers 𝑥𝑖xi and 𝑦𝑖yi (100𝑥𝑖,𝑦𝑖100−100≤xi,yi≤100) — the coordinate of the 𝑖i-th box. It is guaranteed that either 𝑥𝑖=0xi=0 or 𝑦𝑖=0yi=0.

Do note that the sum of 𝑛n over all test cases is not bounded.

Output

For each test case output a single integer — the minimum number of moves required.

[Solution] Traveling Salesman Problem solution codeforces

Example
input

Copy
3
4
0 -2
1 0
-1 0
0 2
3
0 2
-3 0
0 -1
1
0 0
output

Copy
12
12
0

[Solution] Traveling Salesman Problem solution codeforces

In the first test case, a possible sequence of moves that uses the minimum number of moves required is shown below.

(0,0)(1,0)(1,1)(1,2)(0,2)(1,2)(1,1)(1,0)(1,1)(1,2)(0,2)(0,1)(0,0)(0,0)→(1,0)→(1,1)→(1,2)→(0,2)→(−1,2)→(−1,1)→(−1,0)→(−1,−1)→(−1,−2)→(0,−2)→(0,−1)→(0,0)

In the second test case, a possible sequence of moves that uses the minimum number of moves required is shown below.

(0,0)(0,1)(0,2)(1,2)(2,2)(3,2)(3,1)(3,0)(3,1)(2,1)(1,1)(0,1)(0,0)(0,0)→(0,1)→(0,2)→(−1,2)→(−2,2)→(−3,2)→(−3,1)→(−3,0)→(−3,−1)→(−2,−1)→(−1,−1)→(0,−1)→(0,0)

In the third test case, we can collect all boxes without making any moves.

 

For Solution

Click Here

Leave a Comment