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 -1Sample Output 1
3
2Explanation
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()))