MemSQL start[c]up 2.0 Round 1 : B. 4-point polyline

昨年惨敗だったMemSQLだけど今年は不参加。
出てたらレート下がってたし出なくて正解かも？
http://codeforces.com/contest/452/problem/B

問題

整数N,Mが与えられる。
2次元座標上で(0,0)-(N,M)の(N+1)(M+1)個の格子点のうち異なる4つを選択して3つの辺で一列に並べる。
その際３辺の長さの和を最大化する４点を選べ。

解法

当然ながら範囲の対角線に近いものを選ぶほど長くなる。
よって４ツ角の周辺の点を列挙し、総当たりで４点選べばよい。

int N,M;

void solve() {
	int f,i,j,k,l,x,y;
	cin>>N>>M;
	
	vector<pair<int,int> > V;
	V.push_back(make_pair(0,0));	V.push_back(make_pair(1,0));	V.push_back(make_pair(0,1));
	V.push_back(make_pair(N,0));	V.push_back(make_pair(N-1,0));	V.push_back(make_pair(N,1));
	V.push_back(make_pair(0,M));	V.push_back(make_pair(1,M));	V.push_back(make_pair(0,M-1));
	V.push_back(make_pair(N,M));	V.push_back(make_pair(N-1,M));	V.push_back(make_pair(N,M-1));
	
	double ma=0;
	x=0;
	int a,b,c,d;
	FOR(a,V.size()) FOR(b,V.size()) FOR(c,V.size()) FOR(d,V.size()) {
		if(V[a]==V[b] || V[a]==V[c] || V[a]==V[d] || V[b]==V[c] || V[b]==V[d] || V[c]==V[d]) continue;
		if(V[a].first<0 || V[b].first<0 || V[c].first<0 || V[d].first<0) continue;
		if(V[a].second<0 || V[b].second<0 || V[c].second<0 || V[d].second<0) continue;
		if(V[a].first>N || V[b].first>N || V[c].first>N || V[d].first>N) continue;
		if(V[a].second>M || V[b].second>M || V[c].second>M || V[d].second>M) continue;
		double ret=sqrt((V[a].first-V[b].first)*(V[a].first-V[b].first)+(V[a].second-V[b].second)*(V[a].second-V[b].second));
		ret+=sqrt((V[c].first-V[b].first)*(V[c].first-V[b].first)+(V[c].second-V[b].second)*(V[c].second-V[b].second));
		ret+=sqrt((V[c].first-V[d].first)*(V[c].first-V[d].first)+(V[c].second-V[d].second)*(V[c].second-V[d].second));
		if(ret>ma) ma=ret,x=a*1000000+b*10000+c*100+d;
	}
	a=x/1000000;
	b=x/10000%100;
	c=x/100%100;
	d=x%100;
	return _P("%d %d\n%d %d\n%d %d\n%d %d\n",V[a].first,V[a].second,V[b].first,V[b].second,V[c].first,V[c].second,V[d].first,V[d].second);
}

まとめ

パターンは割と限られているので決め打ちでもいいけど、若干コーナーケースがあるので総当たりの方が楽かも。