問題A. アンテナ修復(Google Code Jam Japan 2011 Final)

久しぶりにやったお。

問題A. アンテナ修復

エレメント(線分)の個数Kとエレメントの長さE1〜EKが与えられる。

・すべてのエレメントが同一平面上にある
・すべてのエレメントの + 極が同じ位置にある。これを接続点と呼ぶ
・エレメント同士が重なるのは接続点のみ
・隣り合うエレメントがなす角度はすべて 360/K 度である

隣り合うエレメントの - 極の位置 2 点と接続点で作られる三角形の面積を隣り合うエレメントの組み合わせすべてについて足しあわせた値がアンテナの強度となる。

アンテナの強度を最大化する並べ方での強度を出力せよ。

アルゴリズム

と円形に並べたときのアンテナ強度は、

となる。
並び方を変えてこれを最大化したい場合、
積和を最大化して最後に1/2とsinをかければいい。
大きいもの同士を掛けていくと、積和が最大になりそう。

ほしいのは、並べ方ではなく、アンテナ強度だけなので、ソートして

となった状態で考える。
巡回することに注意して、

のようにから左右に配置していけば強度最大。

コード

javaってプリミティブ型の配列の降順ソートは用意されてないのかな？
C++ならプレディケートgreaterがあるけど...
※
※E[0]から小さい順に左右に配置しても同じなのでそうしてる。
※E[0]とE[1], E[k-1]とE[K-2]の接続を先に計算している。

import java.util.*;
import java.lang.*;

public class CodeJamJapan2011final_A {
	static Scanner scanner;
	public static void main(String[] args) {
		scanner = new Scanner(System.in);
		new CodeJamJapan2011final_A();
	}
	CodeJamJapan2011final_A(){
		int T = scanner.nextInt();
		for(int i=0; i<T; ++i){
			int K = scanner.nextInt();
			int[] E = new int[K];
			for(int j=0; j<K; ++j)
				E[j] = scanner.nextInt();
			
			System.out.println( "Case #" + (i+1) + ": " +solve(K,E) );
		}
	}
	double solve(int K, int[] E){
		Arrays.sort(E);
		int res = E[0]*E[1] + E[K-1]*E[K-2];
		for(int i=0; i+2 < K; i++)
			res += (E[i]*E[i+2]);
		return Math.sin( 2* Math.PI / K ) /2 * res;
	}

}