🔗 Problem #1007

There are $N$ points marked on a plane, and let's call this set of points $P$. A vector matching of set $P$ is a set of vectors, where every vector starts at one point in set $P$ and ends at another point. Also, every point belonging to $P$ must be used exactly once.

The number of vectors in $V$ is half the number of points in $P$.

Given the points on the plane, write a program that outputs the minimum length of the sum of the vectors in the vector matching of set $P$.

The first line contains the number of test cases $T$. Each test case is structured as follows.

The first line of each test case gives the number of points $N$. $N$ is even. From the second line, $N$ lines follow, each giving the coordinates of a point. $N$ is a natural number less than or equal to 20, and the absolute value of each coordinate is an integer less than or equal to 100,000. All points are distinct.

Print the answer for each test case. An absolute/relative error of up to $10^{-6}$ is allowed.

• Input

TC
2
4
5 5
5 -5
-5 5
-5 -5
2
-100000 -100000
100000 100000

• Output

TC
0.000000000000
282842.712474619038

You can form a single vector from two points. Since $N <= 20$, the maximum number of given points is 20. Assuming $N = 20$, the number of vectors we can form is half that, or 10. Depending on how we connect the 20 points, there are many different combinations for creating 10 vectors. Among these possible combinations, calculating the smallest total sum of vectors is the result of this algorithm. (Note this is not calculating the shortest of the 10 vectors.)

The core of this algorithm is calculating, among all the possible ways to form $N / 2$ vectors from $N$ elements, the minimum value. Since the maximum value of $N$ is a very small 20, it's feasible to compare each possibility individually. This is also why the algorithm itself is classified as Brute Force in the first place.

Suppose we have coordinates $(x_1, y_1), (x_2, y_2), (x_3, y_3), (x_4, y_4)$, and from these coordinates we form two vectors $v_1$ and $v_2$ (with the same conditions as in the algorithm problem). Suppose $v_1$ is formed from $(x_1, y_1), (x_2, y_2)$, and $v_2$ is formed from $(x_3, y_3), (x_4, y_4)$. Expressing each vector via its coordinates gives us the following.

$$v_1 = (x_2 - x_1, y_2 - y_1)$$ $$v_2 = (x_4 - x_3, y_4 - y_3)$$

The sum of vectors is simply the sum of the vector coordinates.

In other words, the total sum $v$ can be expressed as follows.

$$v = v_1 + v_2 = (x_2 + x_4 - x_1 - x_3, y_2 + y_4 - y_1 - y_3)$$ $$||v|| = \sqrt{(x_2 + x_4 - x_1 - x_3)^2 + (y_2 + y_4 - y_1 - y_3)^2}$$

The minimum value computed with the formula above is the answer to the algorithm. In other words, we need to combine $(x_1, y_1), (x_2, y_2), (x_3, y_3), (x_4, y_4)$ according to the given condition. We calculate $||v||$ for each combination and return the minimum among them.

Blindly forming all 10 vectors by looping through them won't work. Let's think of a more efficient way to calculate the vectors.

Looking closely at the formula for $v$, you can find a useful characteristic: for each coordinate $x$, $y$, half the coordinates are added and half are subtracted. With 4 coordinates, 2 are added and the other 2 subtracted. What if there were 10? 5 would be added, 5 subtracted.

Using this, what if we computed all combinations of $N / 2$ coordinates out of the total $N$ coordinates? We could divide them into coordinates to be added and coordinates to be subtracted. Then, by adding and subtracting each accordingly, we could easily compute $||v||$.

Therefore, the core of this algorithm is splitting the points in half and finding all the ways to choose points to be used in positive operations versus points to be used in negative operations. Using $_nC_r$ (Combination) makes this easy to compute. Calculate $_nC_{(n / 2)}$, add the chosen coordinates, and subtract the unchosen coordinates.

For example 1, the $_4C_2$ possibilities are as follows.

For this reason, the minimum total sum of vectors in example 1 is 0.

JAVA
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * Baekjoon problem #1007 algorithm class
 *
 * @author RWB
 * @see <a href="https://blog.itcode.dev/posts/2021/06/09/a1007">1007 solution</a>
 * @since 2021.06.09 Tue 00:50:26
 */
public class Main
{
	// Result
	private static double result;
	
	// Whether each element is selected in the current combination
	private static boolean[] isChecked;
	
	// Array of points
	private static int[][] P;
	
	/**
	 * Main function
	 *
	 * @param args: [String[]] arguments
	 *
	 * @throws IOException data input/output exception
	 */
	public static void main(String[] args) throws IOException
	{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		
		// Number of cases
		int T = Integer.parseInt(reader.readLine());
		
		for (int i = 0; i < T; i++)
		{
			// Number of points
			int N = Integer.parseInt(reader.readLine());
			
			result = Double.MAX_VALUE;
			
			isChecked = new boolean[N];
			
			P = new int[N][2];
			
			for (int j = 0; j < N; j++)
			{
				String[] temp = reader.readLine().split(" ");
				
				P[j][0] = Integer.parseInt(temp[0]);
				P[j][1] = Integer.parseInt(temp[1]);
			}
			
			combination(0, N / 2);
			
			System.out.println(result);
		}
		
		reader.close();
	}
	
	/**
	 * Combination function
	 *
	 * @param index: [int] index
	 * @param count: [int] number of elements left to combine
	 */
	private static void combination(int index, int count)
	{
		// If there are no more elements left to combine
		if (count == 0)
		{
			result = Math.min(result, getVector());
		}
		
		// If there are still elements left to combine
		else
		{
			for (int i = index; i < P.length; i++)
			{
				isChecked[i] = true;
				
				combination(i + 1, count - 1);
				
				isChecked[i] = false;
			}
		}
	}
	
	/**
	 * Function that computes the vector magnitude
	 *
	 * @return [double] vector magnitude
	 */
	private static double getVector()
	{
		int x = 0;
		int y = 0;
		
		for (int i = 0; i < P.length; i++)
		{
			// If the point is selected as positive
			if (isChecked[i])
			{
				x += P[i][0];
				y += P[i][1];
			}
			
			// If the point is selected as negative
			else
			{
				x -= P[i][0];
				y -= P[i][1];
			}
		}
		
		return Math.sqrt(Math.pow(x, 2) + Math.pow(y, 2));
	}
}

• Math
• Brute Force Algorithm