Google Code Jam Japan 2011 決勝 A. アンテナ修復

並べ終わった後のエレメントの長さを、E₁, E₂, ……, E_Kとすると、面積は、

　 $http://chart.apis.google.com/chart?cht=tx&chl=%5Cfrac%7B1%7D%7B2%7D%5Csin%5Cleft%28%5Cfrac%7B360%7D%7BK%7D%5Cright%29%5Cleft%28E_1E_2%2BE_2E_3%2B%5Cdots%2BE_%7BK-1%7DE_K%2BE_KE_1%5Cright%29&dummy=.png$

なるべく大きい数同士が隣の方が得だろうと、

1 3 5 8 9 7 6 4 2

という風に並べたら、正解した。

import math

def solve(K,E):
    E = sorted(E)[::-1]
    T = [E[i] for i in range(0,K,2)] + [E[i] for i in range(1,K,2)][::-1]
    ans = sum(T[i]*T[i+1] for i in range(K-1)) + T[-1]*T[0]
    return ans * 0.5 * math.sin(2*math.pi/K)
    
for t in xrange(input()):
    K = input()
    E = map(int,raw_input().split())
    ans = solve(K,E)
    print "Case #%s: %.32f" % (t+1,ans)