TopCoder SRM 738 Div1 Easy FindThePerfectTriangle

色々アプローチがありそうね。
http://community.topcoder.com/stat?c=problem_statement&pm=15109

問題

面積Aと外周Lが与えられる。
格子点を結んでできる３角形のうち、条件を満たすものがあれば構築せよ。

解法

1点を原点に固定し、残り２点を総当たりすることにする（あとで座標が負にならないよう適当にずらす）。
まず、原点からの距離が整数かつ500以内となる点を列挙しよう。そのような点は7000個程度である。
あとはこの7000個から２つ総当たりで選び、面積と周の長さをチェックすればよい。

int sq[1000005];

class FindThePerfectTriangle {
	public:
	vector <int> constructTriangle(int area, int perimeter) {
		ll a,b,c;
		ll A=area;
		
		int i,j,x,y;
		for(i=1;i<=1000;i++) sq[i*i]=i;
		
		
		vector<vector<int>> V;
		for(x=0;x<=500;x++) {
			for(y=0;y<=500;y++) {
				if(sq[x*x+y*y]>0 && sq[x*x+y*y]<500) {
					int s=sq[x*x+y*y];
					V.push_back({x,y,s});
					V.push_back({-x,y,s});
					V.push_back({x,-y,s});
					V.push_back({-x,-y,s});
				}
			}
		}
		
		vector<int> R;
		FOR(i,V.size()) {
			if(V[i][0]<0 || V[i][0]<0) continue;
			FOR(j,V.size()) if(i!=j) {
				int dx=V[i][0]-V[j][0];
				int dy=V[i][1]-V[j][1];
				
				int a=V[i][2];
				int b=V[j][2];
				int s=sq[dx*dx+dy*dy];
				if(s==0 || a+b+s!=perimeter) continue;
				if(a>=b+s) continue;
				if(b>=a+s) continue;
				if(s>=a+b) continue;
				
				
				ll A=V[i][0]*V[j][1]-V[i][1]*V[j][0];
				if(abs(A)!=area*2) continue;
				
				R.push_back(1500);
				R.push_back(1500);
				R.push_back(1500+V[i][0]);
				R.push_back(1500+V[i][1]);
				R.push_back(1500+V[j][0]);
				R.push_back(1500+V[j][1]);
				return R;
				
			}
		}
	}
}

まとめ

一番すっきり解法はなんなんだろうな。