Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2428-42f69184
この記事にトラックバックする(FC2ブログユーザー)

SRM597 DIV1 MEDIUM - ConvexPolygonGame (この記事を編集する[管理者用])

Source

TopCoder SRM597 DIV1 MEDIUM (600pt)
Problem Statement

問題概要

頂点数 $N\ (3 \leq N \leq 50)$ の凸多角形が与えられる.(頂点が反時計回りに与えられる)
各頂点の座標は整数で,絶対値は$10^5$以下.
任意の $3$ 頂点は一直線上にはない.
$2$ 人でゲームをする.行動できなくなったほうが負け.先手必勝か後手必勝かを判定する問題.
各ターンでは,以下の様な凸多角形を作り,次のターンには与えられた凸多角形の代わりにする.
 各頂点は格子点で,与えられた凸多角形の内部,および,周上にある
 各頂点は,与えられた凸多角形の頂点と異なる
 任意の $3$ 頂点は一直線上にない

解法

与えられた多角形の内部に,三角形が作れれば先手の勝ち,そうでなければ後手の勝ち.
なぜなら,後手が打つ手があるなら,その手を先手が打てば良い.(というのを再帰的に繰り返すと後手が打つ手が無い三角形を書ける)
したがって,多角形の内部,および,周上に,一直線上にない $3$ 点が取れるかどうかを判定する問題になる.
基本的には,内部および周上の点を全部列挙して,それらが全て一直線上にあるのかどうかを判定すれば良い.
それは,$x$ 座標を $-10^5$ から $10^5$ まで全部試して,内部の点の $y$ 座標の最大値と最小値を求めれば良い.
ただし,全列挙すると数が多すぎるので,一直線上にあるなら内部の点は高々 $2 \times 10^5$ ぐらいなので,それを超えたらやめるか,
各 $x$ 座標について,数点のみを列挙するなどして適当に端折る必要がある.

C++によるスパゲッティなソースコード
// #includeとusing namespace std;は略

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define ll long long


ll calc_area(ll x1, ll y1, ll x2, ll y2){
  return x1 * y2 - x2 * y1;
}

ll is_in(int n, ll x[], ll y[], ll px, ll py){
  int i;
  ll area;
  rep(i,n){
    area = calc_area(x[i+1]-x[i], y[i+1]-y[i], px-x[i], py-y[i]);
    if(area < 0) return 0;
  }
  rep(i,n) if(x[i]==px && y[i]==py) return 0;
  return 1;
}

class ConvexPolygonGame {
public:
string winner(vector <int> X, vector <int> Y) {
  ll i, j, k, n;
  ll x[100], y[100];
  ll px, py, miny, maxy, tmp;
  vector< pair<ll,ll> > available;

  n = X.size();
  rep(i,n+2) x[i] = X[i%n], y[i] = Y[i%n];

  REP(px,-100000,100001){
    miny =  1000000000;
    maxy = -1000000000;
    rep(i,n){
      if(min(x[i],x[i+1]) <= px && px <= max(x[i],x[i+1])){
        if(x[i]==x[i+1]){
          miny = min(miny, min(y[i], y[i+1]));
          maxy = max(maxy, max(y[i], y[i+1]));
        } else {
          tmp = y[i] + (y[i+1]-y[i])/(double)(x[i+1]-x[i]) * (px-x[i]);
          miny = min(miny, tmp);
          maxy = max(maxy, tmp);
        }
      }
    }
    REP(py, miny-5, maxy+6){
      if( is_in(n, x, y, px, py) )
        available.push_back( make_pair(px, py) );
    }
    if(available.size() > 200010) return "Masha";
  }

  REP(i,2,available.size()){
    if(calc_area(available[1].first - available[0].first, available[1].second - available[0].second, available[i].first - available[0].first, available[i].second - available[0].second))
      return "Masha";
  }

  return "Petya";
}

};

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/2428-42f69184
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。