[Solved] 2-D Point Meeting codechef solution

2-D Point Meeting codechef solution

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(1iN)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,YiK)(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

  • 1T3001≤T≤300
  • 2N1002≤N≤100
  • 109Xi,Yi109−109≤Xi,Yi≤109
  • (Xi,Yi)(Xj,Yj)(Xi,Yi)≠(Xj,Yj) if (ij)(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 (11,11)=(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).

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

Hence after the above operations, the location of the given three points becomes equal to each other.

Test case 22 :

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

  • In the second operation, you choose i=3i=3, and K=2K=−2 and apply the fourth type of operation. So the location of 3rd point becomes (32,1(2))=(1,1)(3−2,−1−(−2))=(1,1).

Hence after the above operations, the location of the given three points becomes equal to each other.


Also read : Airline Restrictions codechef solution

Also read :Travel Pass codechef solution

Also read : Shuffling Parities codechef solution

Also read : XOR Equal codechef solution

2-D Point Meeting codechef solution

No Comments, Be The First!

Your email address will not be published.