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; } };