2-D Point Meeting Solution September Challenge 2021

2-D Point Meeting Solution

You are given N distinct points in a 2-D plane, numbered 1 through N. The X-coordinate of the points are X1,X2,…,XN respectively and the Y-coordinates are Y1,Y2,…,YN respectively. Your goal is to make the location of all the N 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) and a real number K and change the location of the ith point in one of the following ways:

  • Set (Xi,Yi)=(Xi+K,Yi)
  • Set (Xi,Yi)=(Xi,Yi+K)
  • Set (Xi,Yi)=(Xi+K,Yi+K)
  • Set (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 T denoting the number of test cases. The description of T test cases follows.
  • Each test case contains three lines of input.
  • The first line contains a single integer N.
  • The second line contains N space-separated integers X1,X2,…,XN.
  • The third line contains N space-separated integers Y1,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≤300
  • 2≤N≤100
  • −109≤Xi,Yi≤109
  • (Xi,Yi)≠(Xj,Yj) if (i≠j)
  • Sum of N over all test cases does not exceed 600.

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 1:

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

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

Test case 2:

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

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

SOLUTION

Program C: 2-D Point Meeting Solution in 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++: 2-D Point Meeting Solution in 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: 2-D Point Meeting Solution in 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: 2-D Point Meeting Solution in 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()))

September Long Challenge 2021 Solution

Leave a Comment

2 × 5 =