POJ 1319 - Pipe Fitters

http://poj.org/problem?id=1319

概要

a * b の長方形の箱に直径 1 の円を最大でいくつ入れることができるかを答える． a * b の長方形は b * a の長方形とも見なせることに注意．

円の敷き詰め方は grid pattern と skew pattern の2通りに限られる (問題文の図を参照)． 最大となる敷き詰め方が grid か skew のどちらであるかも答える．

制約

解法

grid pattern の場合は floor(a) * floor(b) 個入れることができる．

skew pattern の場合を考える．幅として使うほうを w，高さとして使うほうを h とする．

まず1行にいくつ入るかを考えると，下から奇数行目は floor(w) 個で，偶数行目は floor(w-0.5) 個． 次に何列入るかを考えると，下から1行目は高さ1で，それ以降1行積む毎に sqrt(3)/2 ずつ高さが増えていくので，floor(2*(h-1)/sqrt(3) + 1 個．これで計算することができる．

 1 #include <iostream>
 2 #include <cmath>
 3 using namespace std;
 4 
 5 int grid(double H, double W)
 6 {
 7   return static_cast<int>(H) * static_cast<int>(W);
 8 }
 9 
10 int skew(double H, double W)
11 {
12   static const double SQRT3 = sqrt(3.0);
13   const int h = 2*(H-1)/SQRT3 + 1;
14   const int w1 = W;
15   const int w2 = W-0.5;
16   return ((h+1)/2)*w1 + (h/2)*w2;
17 }
18 
19 int main()
20 {
21   double x, y;
22   while (cin >> x >> y) {
23     const int g = grid(x, y);
24     const int s = max(skew(x, y), skew(y, x));
25     if (g >= s) {
26       cout << g << " grid" << endl;
27     } else {
28       cout << s << " skew" << endl;
29     }
30   }
31   return 0;
32 }
poj/1319.cc