2-D Point Meeting Solution September Challenge 2021

Codechef 2-D Point Meeting 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(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.

Also See: September Long Challenge 2021 Solutions

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).
  • 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,5−5)=(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 (3−2,−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.

Follow us on telegram for quick update an abundance of free knowledge: Click Here

Solution

Program C:

#include<stdio.h>
#include <stdlib.h>
#define ld long double
#define MIN(X, Y) (((X) < (Y)) ? (X) : (Y))
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;
    scanf("%d",&t);
    for (int tc = 0; tc < t ; tc++)
    {
        int n;
        scanf("%d",&n);
        ld arr_x[n], arr_y[n];
        ld h, k;
        for(int i = 0; i < n; i++)
            scanf("%Lf",&arr_x[i]);
        for(int i = 0; i < n; i++)
            scanf("%Lf",&arr_y[i]);
        long min_steps = 100000000000;
        for(int i = 0; i < n; i++)
        {
            for(int l = 0;l < n; l++)
            {
                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));
                h = arr_x[i];
                k = arr_y[l];
                min_steps = MIN(min_steps ,check(h, k, arr_x, arr_y, n));
                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));
                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));
                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));
                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));
                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));
            }
        }
        printf("%ld\n",min_steps);
    }
    return 0;
}

Program C++:

#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;
}

Program Java:

import java.util.*;
import java.lang.*;
import java.io.*;

class Codechef{
	public static void main (String[] args) throws java.lang.Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
        while(T-->0){
            int n = Integer.parseInt(br.readLine());
            String[] X = br.readLine().split(" ");
            String[] Y = br.readLine().split(" ");
            double[] x = new double[n]; double[] y = new double[n];
            for(int i=0;i<n;i++){
                x[i] = Double.parseDouble( X[i] );
                y[i] = Double.parseDouble( Y[i] );
            }
            int ans = Integer.MAX_VALUE;
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    if (i == j) continue;
                    double h = x[i]; double k = y[j];
                    ans = Math.min(ans, solve(h, k, x, y, n));
                    
                    h = (x[i]+x[j]+y[i]-y[j])/2;  k = (x[i]-x[j]+y[i]+y[j])/2;
                    ans = Math.min(ans, solve(h, k, x, y, n));
                    
                    h = x[i] + y[i] - y[j];  k = y[j]; 
                    ans = Math.min(ans, solve(h,k, x, y, n));
                    
                    h = x[i] - y[i] + y[j];   k = y[j]; 
                    ans = Math.min(ans, solve(h, k, x, y, n));    
                }
            }
            System.out.println(ans);
        }    
	}
	static int solve (double h, double k, double x[], double y[], int n){
        int ans = 0 ;
        for (int i = 0; i<n; i++){
            double dx = h - x[i] ;
            double dy = k - y[i] ;
            if (dx == 0 && dy == 0)continue; 
            else if (dx == 0||dy == 0||Math.abs(dx) == Math.abs(dy))  ans++;
            else ans += 2;
        }
        return ans;
	} 
}

Program Python:

from collections import defaultdict
from itertools import product
def f(l1,l2):
    a1,b1,c1=l1
    a2,b2,c2=l2
    det=a1*b2-a2*b1
    det1=c1*b2-c2*b1
    det2=a1*c2-a2*c1
    return (det1/det,det2/det)
def f1(l,s):
    if len(l)==4: l=l[:3]
    elif len(l)==7: l=l[:4]
    return sum(l)-s
for t in range(int(input())):
    n=int(input())
    d1,d2,d3,d4=defaultdict(set),defaultdict(set),defaultdict(set),defaultdict(set)
    for x,y in zip(map(float,input().split()),map(float,input().split())):
        d1[(1,0,x)].add((x,y))
        d2[(0,1,y)].add((x,y))
        d3[(-1,1,y-x)].add((x,y))
        d4[1,1,x+y].add((x,y))
    d={}
    for dct1,dct2 in ((d1,d2),(d1,d3),(d1,d4),(d2,d3),(d2,d4),(d3,d4)):
        for l1,l2 in product(dct1,dct2):
            intersec=f(l1,l2)
            if intersec in d: 
                d[intersec][0].append(len(dct2[l2]))
                if intersec in dct2[l2]: d[intersec][1]=2
            else:
                d[intersec]=[[len(dct1[l1]),len(dct2[l2])],2*(intersec in dct2[l2])]
    print(2*n-max(f1(*el) for el in d.values()))

Codechef Long Challenges

September Long Challenge 2021 Solution

August Long Challenge 2021 Solutions

Leave a Comment