プロジェクトオイラー Problem 247 「双曲線下の正方形」 †

Problem 247 「双曲線下の正方形」 †

1 ≤ x, 0 ≤ y ≤ 1/x の領域について考える.

S1 をこの曲線の下に入る最大の正方形とする.
S2 を残りの空間に入る最大の正方形とし, これを繰り返す.
Sn のインデックスを (left, below) とする. left は Sn の左にある正方形の数を, below は Sn の下にある正方形の数を表す.

これらの正方形に番号を記したものを上の図に示す.
S2 は左に 1 個, 下に 0 個の正方形があるので, S2 のインデックスは (1,0) である.
S32 のインデックスは (1,1) であることがわかる. S50 のインデックスも同じである.
50 は (1,1) をインデックスに持つ Sn の中で, 最大の n である.

(3,3) をインデックスに持つ Sn の中で, 最大の n を求めよ.

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20247




解法
正方形の左下をx1,y1とすると
y=x-x1+y1とy=1/x交点のＸ座標とｙ１、交点のｙ座標とx1が次の正方形の位置となります。
交点のｘ座標と右下のｘ1の差が正方形のサイズです。
これを優先順位付きキューに入れて３、３がでてきた回数を調べます。
後は３，３のインデックスを持つ箱の積み上げかたは再帰関数で考えて
1  1  1  1
1  2  3.  4
1  3  6 10
1 4 10  20
で20通りしかありえないので20個めの3,3インデックス正方形が答えです。



#include<stdio.h>
#include<math.h>
#include<queue>

struct S{
      double x1,y1,size;
      int down,left;
      bool operator<(const S& s)const{
            return size<s.size;
      }
};

double calcSize(S& s1){
      double x1=s1.x1;
      double y1=s1.y1;
      return (-y1+x1+sqrt((y1-x1)*(y1-x1)+4))/2.0-s1.x1;
}

int main(){
      S s1,s2;
      s1.x1=1;
      s1.y1=0;
      s1.size=calcSize(s1);
      s1.down=0;
      s1.left=0;
      int count=0,count33=0;
      std::priority_queue<S> pq;
      pq.push(s1);
      while(1){
            s2=s1=pq.top();
            pq.pop();
            count++;
            if(s1.down==3&&s1.left==3)count33++;
            if(count33==20)break;
            s2.x1+=s1.size;
            s2.size=calcSize(s2);
            s2.left++;
            pq.push(s2);

            s2=s1;
            s2.y1+=calcSize(s2);
            s2.down++;
            s2.size=calcSize(s2);
            pq.push(s2);
      }
      printf("%d\n",count);
}