Codechef September long challenge 2021 | 2-D Point Meeting Solution

 

Codechef September long challenge 2021 | 2-D Point Meeting Solution

-TechTalkBot

You are given NN distinct points in a 22-D plane, numbered 11 through NN. The X-coordinate of the points are X1,X2,…,XNX1,X2,…,XN respectively and the Y-coordinates are Y1,Y2,…,YNY1,Y2,…,YN respectively. Your goal is to make the location of all the NN points equal to that of each other. To achieve this, you can do some operations.

In one operation, you choose an index i(1≤i≤N)i(1≤i≤N) and a real number KK and change the location of the ithith point in one of the following ways:

• Set (Xi,Yi)=(Xi+K,Yi)(Xi,Yi)=(Xi+K,Yi)
• Set (Xi,Yi)=(Xi,Yi+K)(Xi,Yi)=(Xi,Yi+K)
• Set (Xi,Yi)=(Xi+K,Yi+K)(Xi,Yi)=(Xi+K,Yi+K)
• Set (Xi,Yi)=(Xi+K,Yi−K)(Xi,Yi)=(Xi+K,Yi−K)

Find the minimum number of operations to achieve the goal.

Input Format

• The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
• Each test case contains three lines of input.
• The first line contains a single integer NN.
• The second line contains NN space-separated integers X1,X2,…,XNX1,X2,…,XN.
• The third line contains NN space-separated integers Y1,Y2,…,YNY1,Y2,…,YN.

Output Format

For each test case, print a single line containing one integer – the minimum number of operations to achieve the goal.

Constraints

• 1≤T≤3001≤T≤300
• 2≤N≤1002≤N≤100
• −109≤Xi,Yi≤109−109≤Xi,Yi≤109
• (Xi,Yi)≠(Xj,Yj)(Xi,Yi)≠(Xj,Yj) if (i≠j)(i≠j)
• Sum of NN over all test cases does not exceed 600600.

Subtasks

Subtask #1 (100 points): original constraints

Sample Input 1 

2
3
0 1 -4
0 1 5
3
0 1 3
1 1 -1

Sample Output 1 

3
2

Explanation

Test case 11 :

• In the first operation, you choose i=2i=2, and K=−1K=−1 and apply the third type of operation. So the location of 2nd2nd point becomes (1−1,1−1)=(0,0)(1−1,1−1)=(0,0).

• In the second operation, you choose i=3i=3, and K=4K=4 and apply the first type of operation. So the location of 3rd3rd point becomes (−4+4,5)=(0,5)(−4+4,5)=(0,5).