AOJ 2635 「Snuke」
この記事はAOJ-ICPC Advent Calendar 2015の記事として書かれました。
りんごさんセットのSnake解きました。
解法を知っていれば簡単。
解法
ネタバレのため、反転してます
各辺について注目した時、(凸包)ー(凸包)という鉄アレイみたいな形状になっていれば良い。
先頭から見ていき、0~i番目までの頂点の凸包=0~i+1番目までの頂点の凸包となっている部分があってはダメ。
さらに、前後を逆にして同様の判定を行う。
コード
// 前略 bool f(Poly p) { int n = sz(p); double pre = -1; rep(i,n) if (i >= 2) { Poly a; rep(j,i+1) a.pb(p[j]); a = convex(a); double now = area(a); if (abs(now-pre) < eps) return false; pre = now; } return true; } int main() { int n; cin >> n; Poly p(n); rep(i,n) cin >> p[i].x >> p[i].y; string ans = "Possible", im = "Impossible"; if (!f(p)) ans = im; reverse(rng(p)); if (!f(p)) ans = im; cout<<ans<<endl; return 0; }
自分を通す(至言)
— すぎむ (@sugim48) December 6, 2015