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

  September Challenge 2021 (Rated for Div 3)

                                    Scorable Problems for Division 3

Name	Code	Successful Submissions	Accuracy
Airline Restrictions	AIRLINE
Travel Pass	TRAVELPS
Shuffling Parities	SHUFFLIN
XOR Equal	PALINT
Minimize Digit Sum	MNDIGSUM
2-D Point Meeting	POINTMEE
Covaxin vs Covishield	COVAXIN
Treasure Hunt	TREHUNT
Minimum Digit Sum 2	MNDIGSM2

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

• Post published:September 4, 2021
• Post category:Coding
• Post comments:0 Comments

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).

C++ Solution

#include<bits/stdc++.h>

using namespace std;

#define ld long double

int check(ld h,ld k,ld arr_x[],ld arr_y[],int n){

int steps = 0;

for(int j=0;j<n;j++){

ld xx=h-arr_x[j];

ld yy=k-arr_y[j];

if(xx==0 && yy==0){

steps+=0;

}

else if((xx==0 && yy!=0) || (xx!=0 && yy==0) ){

steps+=1;

}

else if(abs(xx)==abs(yy)){

steps+=1;

}

else steps+=2;

}

return steps ;

}

int main(){

int t;cin>>t;

while(t--){

int n;cin>>n;

ld arr_x[n],arr_y[n];

ld h,k;

for(int i=0;i<n;i++){

cin>>arr_x[i];

}

for(int i=0;i<n;i++){

cin>>arr_y[i];

}

int min_steps=INT_MAX;

for(int i=0;i<n;i++){

for(int l=0;l<n;l++){

//mean_point

h=(arr_x[i]+arr_x[l])/2;

k=(arr_y[i]+arr_y[l])/2;

min_steps=min(min_steps,check(h,k,arr_x,arr_y,n));

//x & y intersection points

h = arr_x[i];

k = arr_y[l];

min_steps=min(min_steps,check(h,k,arr_x,arr_y,n));

//x+y=c1 and x-y=c2 intersection points

ld c1=arr_x[i]+arr_y[i];

ld c2=arr_x[l]-arr_y[l];

h = (c1+c2)/2;

k = (c1-c2)/2;

min_steps=min(min_steps,check(h,k,arr_x,arr_y,n));

//x+y=c and x intersection

ld c3=arr_x[i]+arr_y[i];

h = arr_x[l];

k = c3-h;

min_steps=min(min_steps,check(h,k,arr_x,arr_y,n));

//x+y and y intersection

ld c4=arr_x[i]+arr_y[i];

k = arr_y[l];

h = c4-k;

min_steps=min(min_steps,check(h,k,arr_x,arr_y,n));

//x-y and X

ld c5=arr_x[i]-arr_y[i];

h = arr_x[l];

k = h-c5;

min_steps=min(min_steps,check(h,k,arr_x,arr_y,n));

//x-y and y

ld c6=arr_x[i]-arr_y[i];

k = arr_y[l];

h = c6+k;

min_steps=min(min_steps,check(h,k,arr_x,arr_y,n));

}

}

cout<<min_steps<<"\n";

}

return 0;

}