AOJ 1186 Integral Rectangles (ICPC国内予選2013問題A)

• 問題文

正整数w, h(1 <= w, h <= 100 かつ h < w)が与えられ, (w^2 + h^2, h)と(W^2 + H^2, H)を辞書式順序で比較した際に(H < W)かつ(w^2 + h^2, h)以上で最小の(W^2 + H^2, H)を求め、H, Wを出力する問題です。

解のW, Hはともに150以下であることが保証されているので1以上150以下でH < Wを満たす任意のW, Hについて比較して調べるとよいです。
ペアの比較はC++ならpairを使うと最初から比較が辞書式順序になっているので楽です。

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

typedef pair<int,int> P;

int main(){
    int w, h;
    while( cin >> h >> w , h || w ){
        pair<P,int> p(P(w*w + h*h, h), w);
        vector<pair<P,int> > v;
        for(int h_ = 1; h_ <= 150; h_++){
            for(int w_ = 1; w_ <= 150; w_++){
                if( h_ < w_ ){
                    v.push_back( pair<P,int>(P(w_*w_ + h_*h_, h_), w_) );
                }
            }
        }
        sort(v.begin(), v.end());
        for(int i = 0; i < v.size(); i++){
            if( p < v[i] ){
                cout << v[i].first.second << " " << v[i].second << endl;
                break;
            }
        }
    }
}