AOJ 2635 「Snuke」

この記事はAOJ-ICPC Advent Calendar 2015の記事として書かれました。

りんごさんセットのSnake解きました。

解法を知っていれば簡単。

問題概要

http://judge.u-aizu.ac.jp/onlinejudge/IMAGE2/JAGSummer2014/sunake.png

通れるでしょうか?

解法

ネタバレのため、反転してます

各辺について注目した時、(凸包)ー(凸包)という鉄アレイみたいな形状になっていれば良い。
先頭から見ていき、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;
}