長さが異なるK本のアンテナを等角度間隔に配置した時の面積の最大化.
方針
- すべてのアンテナの配置について計算するのは非効率.
- 大きな三角形から順に作っていけば,最大になるはず.
- ソートして大きいものから順にすでに配置されているアンテナの右側か左側に配置していく.
ソースコード
import math with open("input.txt") as f: T = int(f.readline().strip()) for i in xrange(T): K = int(f.readline().strip()) A = 0 E = map(int, f.readline().strip().split(" ")) E.sort() t = [] t.append([E.pop(), 0]) while len(E) >= 1: A += t[0][0] * E[-1] t[0][1] += 1 if t[0][1] >= 2: t.pop(0) t.append([E.pop(), 1]) A += t[0][0] * t[1][0] print "Case #" + str(i + 1) + ": " + str(A * math.sin(2*math.pi / K) / 2)