Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-10-08Google Code Jam Japan 2011 決勝

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

| 20:56 | Google Code Jam Japan 2011 決勝 A アンテナ修復 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - Google Code Jam Japan 2011 決勝 A アンテナ修復 - SRM diary(Sigmar) Google Code Jam Japan 2011 決勝 A アンテナ修復 - SRM diary(Sigmar) のブックマークコメント

Problem Statement

解答方針

Bから浮気してきた

よく分からんけど大きいやつ同士をくっつけたほうが面積大きくなるだろ

Greedyに大きいのをくっつけるコードを書いた。

small通った。

largeも通った。

何かBと比べてえらい簡単だな・・・


ソースコード

double solve(int K, vector <int> &E) {
	double res=0;
	
	sort(E.begin(), E.end(), greater <int>());
	res=(double)E[0]*E[1];
	double e0=E[0], e1=E[1];
	for(int i=2; i<K; i++) {
		res+=e0*E[i];
		e0=e1; e1=E[i];
	}
	res+=e0*e1;
	res*=sin(2*M_PI/K)/2;
	return res;
}

int main() {
	ifstream ifs("input.txt");
	ofstream ofs("output.txt");

	int testcase;
	ifs >> testcase; ifs.ignore();
	for(int testnum=1; testnum<=testcase; testnum++) {
		int K;
		ifs >> K;
		vector <int> E(K);
		for(int i=0; i<K; i++) ifs >> E[i];
		double res=solve(K, E);
		ofs << "Case #" << fixed << setprecision(15) << testnum << ": ";
		ofs << res << endl;
	}
}

NiiqiitoNiiqiito2013/02/17 11:57I hate my life but at least this makes it braeable.

xkhqsmsgifxkhqsmsgif2013/02/19 15:16E9CxwG <a href="http://cdmchajbiebt.com/">cdmchajbiebt</a>

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20111008