Codeforces #378 Div2 D. Kostya the Sculptor

色々やり方ありそう。
http://codeforces.com/contest/733/problem/D

問題

N個の直方体がある。
これらの直方体に内接する最大の球の半径を求めたい。
ここで、ある面の大きさが等しい２つの長方形があれば、全部で１回だけその面で直方体を連結できるとする。

最大の球を得られる直方体を１つまたは２つ答えよ。

解法

2辺をキーとし、値として残り1辺の集合をとするmapを作って、各直方体に対し３通りの面で同じ面がないか判定していく。
同じ面を持つ直方体があったら、残り１辺が最長のものとペアにしよう。

int N;
int A[101010],B[101010],C[101010];
pair<int,int> AB[101010],BC[101010],CA[101010];
int X,Y;
int ma;
map<pair<int,int>,pair<int,int>> M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	X=-1,Y=-1;
	FOR(i,N) {
		cin>>A[i]>>B[i]>>C[i];
		if(min(A[i],min(B[i],C[i]))>ma) X=i+1, ma=min(A[i],min(B[i],C[i])), Y=-1;
		AB[i]={min(A[i],B[i]),max(A[i],B[i])};
		BC[i]={min(B[i],C[i]),max(B[i],C[i])};
		CA[i]={min(C[i],A[i]),max(C[i],A[i])};
		
		if(M[AB[i]].first>0) {
			x = min(A[i],min(B[i],C[i]+M[AB[i]].first));
			if(x>ma) ma=x, X=i+1, Y=M[AB[i]].second+1;
		}
		if(M[BC[i]].first>0) {
			x = min(A[i]+M[BC[i]].first,min(B[i],C[i]));
			if(x>ma) ma=x, X=i+1, Y=M[BC[i]].second+1;
		}
		if(M[CA[i]].first>0) {
			x = min(A[i],min(B[i]+M[CA[i]].first,C[i]));
			if(x>ma) ma=x, X=i+1, Y=M[CA[i]].second+1;
		}
		
		M[AB[i]]=max({M[AB[i]],{C[i],i}});
		M[BC[i]]=max({M[BC[i]],{A[i],i}});
		M[CA[i]]=max({M[CA[i]],{B[i],i}});
	}
	
	if(Y==-1) _P("%d\n%d\n",1,X);
	else _P("%d\n%d %d\n",2,X,Y);
	
}

まとめ

もっとすんなり書けそう。