TopCoder SRM 599 Div1 Medium FindPolygons

問題

全ての頂点が格子点であるような、単純多角形で、周の長さがLであるものを考える。
これらのうち、頂点数が最も少ないものであって、それが複数あるときは
最も長い辺と短い辺の長さの差が最小であるものを求めよ。


答えには最も長い辺と短い辺の長さの差の最小値を出力せよ。

制約条件

単純多角形とは、自己交差がなく、どの連続する2辺も同一直線上にない多角形。
L≦5000の整数

方針

奇数はダメなのはわかっていたのに、長方形で必ず作れることを見落としててアホだった。


整数でない辺があるときは長さは√xという感じなので、どれだけ足しても整数にはならない。
なので、全ての辺の長さは整数。


まず、Lが奇数のときは、どうやっても無理。
何故なら、ピタゴラス数のパリティを考えると
(c, a, b) = (奇数, 偶数, 奇数) または(奇数, 奇数, 偶数), または全部偶数しかなくて、
図形は一周したときにx, yはもとの場所に戻っていないといけないから、
(奇数, 偶数, 奇数)のパターンは偶数回、(奇数, 奇数, 偶数)のパターンも偶数回しか使えないため。


Lが偶数のときはL=2のときはどうやっても無理だが、それ以外は必ず長方形で作れる。
L=4mだったら一辺mの正方形でよくて、
L=4m+2だったら一辺mとm+1の長方形でいい。


なので、三角形で作れるかどうかを判定するだけの問題になる。
これはピタゴラス数を全列挙しておいて、二辺を固定して、あとの一辺は二分探索で探すとかやればいいだけ。定数倍が少しシビアだけど。

ソースコード

#define F first
#define S second
class FindPolygons {
	public:
	double minimumPolygon(int L) {
		
		int ans = inf;
		
		vector<pair<int, pi> > v;
		for(int i = 1; i <= 2500; i++) for(int j = 1; j <= i; j++){
			 //if(__gcd(i, j) != 1) continue;
			int l2 = i * i + j * j;
			int l = sqrt(l2) + 0.5;
			if(l > 2500 + EPS || l * l != l2) continue;
			
			v.pb(mp(l, mp(i, j)));
		}
		sort(all(v));
		
		rep(i, v.size()){
			if(L == v[i].F + v[i].S.F + v[i].S.S) ans = min(ans, v[i].F - v[i].S.S);
		}
		rep(i, v.size()) rep(j, i + 1){
			if(v[i].F + v[j].F >= L) break;
			rep(k, 4) rep(s, 2){
				int a = v[i].S.F, b = v[i].S.S;
				int c = v[j].S.F, d = v[j].S.S;
				
				if(s) swap(c, d);
				
				if(k & 1) a *= -1;
				if(k & 2) b *= -1;
				a = abs(a + c); b = abs(b + d);
				
				int l2 = a * a + b * b;
				int l = sqrt(l2) + 0.5;
				if(l * l != l2 || v[i].F + v[j].F + l != L) continue;
				
				if(a < b) swap(a, b);
				
				if(binary_search(all(v), mp(l, mp(a, b)))){
					vi t;
					t.pb(v[i].F); t.pb(v[j].F); t.pb(l);
					sort(all(t));
					if(t[0] + t[1] + t[2] == L && t[2] < t[0] + t[1]) ans = min(ans, t[2] - t[0]);
				}
				
				if(b == 0){
					vi t;
					t.pb(v[i].F); t.pb(v[j].F); t.pb(l);
					sort(all(t));
					if(t[0] + t[1] + t[2] == L && t[2] < t[0] + t[1]) ans = min(ans, t[2] - t[0]);
				}
			}
		}
		if(ans == inf){
			if(L % 4 == 0) ans = 0;
			else if(L > 2 && L % 2 == 0) ans = 1;
			else ans = -1;
		}
		return ans;
	}
};