Maximizing Projected Matching Distance

In a 3-dimensional space, you are given n black points and n white points. For any one‐to‐one correspondence (a permutation) between the black and white points, we define the movement distance as the sum of Euclidean distances of the n pairs. Among all n! possible correspondences, the movement distance is defined to be the minimum possible sum of distances.

You are allowed to project all the 3D points onto a k-dimensional subspace, where k is either 1 or 2. A 1D subspace is a line in 3D and a 2D subspace is a plane in 3D. The projection of a point onto the subspace is defined as the unique point in the subspace that minimizes the Euclidean distance to the original point. For example, projecting the four points (0,0,0), (1,1,0), (1,0,0), and (0,1,0) onto the line defined by the intersection of the planes x-y=0 and z=0 gives the projected points (0,0,0), (1,1,0), (0.5,0.5,0), and (0.5,0.5,0) respectively.

Your goal is to choose a k-dimensional subspace upon which the movement distance (after projecting all points and then computing the minimum matching pairing cost) is maximized. You are then asked to output the maximum movement distance divided by n.

The optimal matching in the projected space is defined as follows:

• For k = 1: After projecting, let the black points (and similarly the white points) have scalar coordinates. The optimal matching is achieved by pairing the points in sorted order; i.e., if b₁, b₂, …, b_n and w₁, w₂, …, w_n are the sorted projections of the black and white points respectively, then the matching cost is
  
  $$f(u)=\sum_{i=1}^{n}|b_i - w_i|.$$</p>
  • For k = 2: After projecting, every point becomes a 2D point. The optimal matching is defined as the pairing between black and white points which minimizes the sum of Euclidean distances in the plane. This can be computed using a minimum cost bipartite matching algorithm (for example, the Hungarian algorithm).

  You are given the value of k along with the coordinates of the n black points and n white points. Compute

  $$\frac{\max_{S\in \mathcal{S}_k} \min_{\pi\in S_n} \sum_{i=1}^{n} \|P_S(b_i)-P_S(w_{\pi(i)})\|_2}{n}, $$

  where P_S(p) denotes the orthogonal projection of point p onto subspace S and \( \mathcal{S}_k \) is the set of all k-dimensional subspaces of \(\mathbb{R}^3\).

  Hint: "Change your angle, and the world might be different." In other words, by selecting a suitable subspace (or “angle”), you can maximize the matching distance.

  inputFormat

  The input is given as follows:

   n k
   b1,x b1,y b1,z
   b2,x b2,y b2,z
   ...
   bn,x bn,y bn,z
   w1,x w1,y w1,z
   w2,x w2,y w2,z
   ...
   wn,x wn,y wn,z
  

  Here n (1 ≤ n ≤ 10) is the number of black points (and also white points), and k is either 1 or 2.

  outputFormat

  Output a single number – the maximum possible value of the movement distance divided by n. An absolute or relative error of up to 10^-6 is acceptable.

  sample

  3 1
  1 0 0
  2 0 0
  3 0 0
  4 0 0
  5 0 0
  6 0 0
  

  3.000000
  

  </p>