[伯俊]#1007後マッチング

質問する

平面上にN個の点があり、その点を集合Pと呼ぶ.集合Pのベクトルマッチングはベクトルの集合であり,すべてのベクトルは集合Pの一方の点から他方の点までのベクトルの集合である.また、Pに属するすべての点を1回書きます.
V上のベクトルの個数はP上の点の半分である.
平面上の点が与えられると、集合Pのベクトルマッチングにおけるベクトルの和の長さの最大値を出力するプログラムが作成される.

入力

第1行は、試験例の個数Tを与える.各テストケースは、次のように構成されています.
テストケースの最初の行は、点の個数Nを与える.Nは偶数です.2行目からN行に点の座標を与えます.Nは20以下の自然数であり、座標は節気値が100000以下の整数である.点ごとに違います.

しゅつりょく

各テスト・インスタンスは正解を出力します.絶対/相対誤差は10^(-6)まで許容される.

入力例1

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

サンプル出力1

0.000000000000
282842.712474619038

に答える

この問題はdfs(深さ優先探索)アルゴリズムで解くことができる.また,数学的な問題解決も必要であり,ベクトル和を求めるためには,まず全体のベクトル和を求め,その後N/2点を定め,その後ベクトルの長さを求めればよい.

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

public class Main {
    static int[] x_arr;
    static int[] y_arr;
    static int N;
    static double min;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        for(int i=0; i<T; i++) {
            N = Integer.parseInt(br.readLine());
            x_arr = new int[N];
            y_arr = new int[N];
            min = Double.MAX_VALUE;
            long sum_x = 0;
            long sum_y = 0;

            for(int j=0; j<N; j++) {
                String[] input = br.readLine().split(" ");
                int x = Integer.parseInt(input[0]);
                int y = Integer.parseInt(input[1]);
                x_arr[j] = x;
                y_arr[j] = y;

                sum_x += x;
                sum_y += y;
            }

            dfs(sum_x, sum_y, 0, 0);

            System.out.println(min);
        }
    }

    public static void dfs(long sum_x, long sum_y, int idx, int cnt) {
        if(N-idx+cnt<N/2) return;

        if(cnt==N/2) {
            min = Math.min(min, Math.sqrt(sum_x*sum_x+sum_y*sum_y));
            return;
        }

        for(int i=idx; i<N; i++) {
            long next_sumX = sum_x - 2*x_arr[i];
            long next_sumY = sum_y - 2*y_arr[i];

            dfs(next_sumX, next_sumY, i+1, cnt+1);
        }
    }
}