PKU 1319 Pipe Fitters

http://poj.org/problem?id=1319
m*nの長方形領域に直径1の円を重なりがないようにいくつ詰め込めるかとその時の詰め方をこたえろような問題。

m,nが小さいので愚直にシミュレーション。

int skew(double n,double m){
  int ret=0;
  for(int i=1;;++i){
    double he=0.5+sqrt(3)/2*(i-1);
    if(he+0.5>n)break;
    for(int j=1;;++j){
      double wi=j-i%2*0.5;
      if(wi+0.5>m)break;
      ++ret;
    }
  }
  return ret;
}

main(){
  double n,m;
  while(cin>>n>>m){
    string ans="grid";
    int an=int(n+EPS)*int(m+EPS);
    rep(i,2){
      int sk=skew(n,m);
      swap(n,m);
      if(sk>an){
	an=sk;
	ans="skew";
      }
    }
    cout<<an<<' '<<ans<<endl;
  }
}