2-D Point Meeting solution codechef

2-D Point Meeting solution codechef

For Solution

Click Here!

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: 2-D Point Meeting solution codechef

  • 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 2-D Point Meeting solution codechef

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-D Point Meeting solution codechef 

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

Sample Output 1 2-D Point Meeting solution codechef 

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.

For Solution

Click Here!

Leave a Comment

Your email address will not be published.