https://www.acmicpc.net/problem/1007

아이디어

적절하게 $(i, j)$의 쌍을 선택했을 때 시점이 $\mathrm{p}_i$, 종점이 $\mathrm{p}_j$인 벡터는 $\mathrm{p}_j-\mathrm{p}_i$이다.
($i \in I$, $j \in J$가 속한 집합의 제약조건을 나타내자면, $\left\{I, J\right\}$가 $P$의 분할이고 $\#I=\#J=N/2$이라 할 수 있다.)

이때, 구하는 합은 다음과 같이 분해할 수 있다.

$\sum_{(i, j)}\left(\mathrm{p}_j-\mathrm{p}_i\right) = \sum_{j}\mathrm{p}_j - \sum_i\mathrm{p}_i$

즉, 시점과 종점이라는 구분 외에 두 점이 어떤 벡터로 연결되어 있는지는 관계가 없음을 알 수 있다.

$N$개의 점 중 $N/2$개의 점을 시점으로 하고 나머지를 종점으로 하는 모든 경우에 대해 벡터의 합을 구하고 그 중 최솟값을 찾으면 된다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer tk = null;

    static int T;
    static int N;
    static int[] X, Y;

    static double ans;

    public static void main(String[] args) throws Exception {
        T = Integer.parseInt(rd.readLine());
        for (int t=0; t<T; t++) {
            ans = Double.MAX_VALUE;

            N = Integer.parseInt(rd.readLine());

            X = new int[N];
            Y = new int[N];

            for (int i=0; i<N; i++) {
                tk = new StringTokenizer(rd.readLine());
                X[i] = Integer.parseInt(tk.nextToken());
                Y[i] = Integer.parseInt(tk.nextToken());
            }

            for (int mask = 0; mask < (1 << N); mask++) {
                if (Integer.bitCount(mask) != N/2) continue;

                // sum vector
                double sx = 0;
                double sy = 0;
                for (int i=0; i<N; i++) {
                    if (((mask >> i) & 1) == 1) {
                        // (X[i], Y[i]) to be some vector's start point
                        sx -= X[i];
                        sy -= Y[i];
                    }
                    else {
                        // endpoint
                        sx += X[i];
                        sy += Y[i];
                    }
                }
                ans = Math.min(ans, Math.sqrt(sx*sx + sy*sy));
            }
            sb.append(ans).append('\n');
        }
        System.out.println(sb);
    }
}

메모리 및 시간

• 메모리: 17012 KB
• 시간: 392 ms