UVa 432 - Modern Art - primia -log

http://uva.onlinejudge.org/external/4/432.html

問題

有名な画家、Mel Borp は、Modern Art の新しい実験主義的なスタイル(?)を伝えるすばらしい作品集を製作している。一見すると、これらの作品は単純なように見える。なぜなら異なる大きさの三角形で構成されていて、それらが積み重なっているように見えるだけだからだ。だが、これらの作品は、おどろくべき量の思考、計算、そして精密さを必要とする。なぜならすべての三角形はキャンバスを離れることなく描かれているからだ。メルがどのように、正確に作品を描いているかはしっかり守られている秘密だ。

最近、彼は新たなシリーズに着手した。それはT0,0という小さな三角形だった。その後、彼はT1,1を作った、彼の作品の基礎となるものだ。

それから彼は試験的に一段階発展させることを決めて、T1,2とT3,2を描いた。
するとTp,qという題名から絵の形は次のように推測されることに気づく。

T0,0 はひとつだけの三角形
T1,1 は一回り小さい逆三角形をT0,0の内部に含む。したがって4つの小さな三角形から構成される
もし p > 0 かつ q > 1 であれば、絵はTp,q-1のような感じになる。ただし右下の三角形を4つに分割するような逆三角形がその内部に配置される
もし p > 1 かつ q > 0 であれば、Tp-1,qにおいて左下の三角形を逆三角形で分割する
他の p, q は不正

作品の三角形はすべて同じに見える（それぞれの三角形は二等辺三角形）が、高さと幅はメルの使うキャンバスの大きさによる。

メルはシリーズを非常に複雑な絵になるT10,10で終わらせたいと思い、描き上げることは可能だろうとも思った。しかし何度試しても正しくできなかった。そして彼は、あなたなら絵の線の始点と終点を順番に出力するプログラムを書いて助けてくれるだろうと思った。もちろんあなたはメルが彼の作品がどのように描かれているのかを知る必要があるだろう。そこで我々は彼の秘密の技術を明らかにしよう。

たとえとして、T1,2を見てみよう。
メルはいつも三角形のてっぺんから始める。直線を左下の三角形の左下頂点まで描き、続けてその三角形の右下頂点まで伸ばす。次にその三角形の頂上まで線を描く。ここで彼は始めた点に戻るか、もうひとつ別の三角形の左下の頂点に到達する。後者の場合、彼はその三角形の底辺を描き、その後　その三角形の右下頂点以下に位置する（複数の）三角形で同じように作業をはじめる（繰り返す）。

コード

#include<iostream>
#include<vector>
#include<cmath>
#include<complex>
#define MAX_SIZE 16

using namespace std;

typedef complex<int> point;
typedef vector<point> sequence;

sequence inverted_triangles[MAX_SIZE];

sequence InvertedTriangle( point base, int size ){
  sequence ret;
  int new_x = base.real()/(1<<(size));
  int new_y = base.imag()/(1<<(size));
  ret.push_back( point( 0, 0 ) );
  ret.push_back( point( -new_x, new_y ) );
  ret.push_back( point( new_x, new_y ) );
  ret.push_back( point( 0, 0 ) );
  return ret;
}

void ComputeInvertedTriangles( point base ){
  for(int i = 1; i < MAX_SIZE; ++i){
    inverted_triangles[i] = InvertedTriangle( base, i );
  }
}

void AddBottomLeftTriangle(int size, sequence &s){
  sequence inv_tri = inverted_triangles[ size ];
  for(unsigned int i = 0; i < inv_tri.size(); ++i){
    int new_x = inv_tri[i].real() + s[0].real() / ( 1<<(size-1) );
    inv_tri[i].real() = new_x;
  }
  s.insert( s.begin() + 2, inv_tri.begin(), inv_tri.end() );
}

void AddBottomRightTriangle(int size, sequence &s){
  sequence inv_tri = inverted_triangles[ size ];
  for(unsigned int i = 0; i < inv_tri.size(); ++i){
    int new_x = inv_tri[i].real() + ( (1<<size)-1 ) * ( s[0].real() / (1<<(size-1)) );
    inv_tri[i].real() = new_x;
  }
  s.insert( s.end() - 1, inv_tri.begin(), inv_tri.end() );  
}

void ModernArt( int p, int q, point base, sequence &ret ){
  int now_p, now_q;
  ret.push_back( base );
  ret.push_back( point(0,0) );
  ret.push_back( point(2*base.real(),0) );

  if( p == 0 && q == 0 ){
    return ;
  }

  AddBottomLeftTriangle( 1, ret );
  now_p = 1;
  now_q = 1;

  while( true ){
    if( now_p == p || now_q == q ) break;
    AddBottomLeftTriangle( now_p+1, ret );
    AddBottomRightTriangle( now_q+1, ret );
    ++now_p;
    ++now_q;
  }
  if( p > q ){
    while( p != now_p ){
      AddBottomLeftTriangle( now_p + 1, ret );
      ++now_p;
    }
  }else if( q > p ){
    while( q != now_q ){
      AddBottomRightTriangle( now_q + 1, ret );
      ++now_q;
    }
  }
}

int main(){
  int n;
  cin >> n;
  for(int tc = 0; tc < n; ++tc ){
    int p,q,x,y;
    sequence ans;

    scanf("%d%d%d%d", &p, &q, &x, &y);
    ComputeInvertedTriangles( point(x,y) );
    ModernArt( p, q, point(x, y), ans );

    for(unsigned int i = 0; i < ans.size() - 1; ++i){
      printf("(%d,%d)(%d,%d)\n", ans[i].real(), ans[i].imag(), ans[i+1].real(), ans[i+1].imag());
    }
    printf("(%d,%d)(%d,%d)\n\n", ans.back().real(), ans.back().imag(), ans[0].real(), ans[0].imag());
  }
  return 0;
}

コードの概要

ボトムアップな感じでどんどん作品を発展させる。追加すべき描き順を追加すべき場所に挿入していく。printf は TLE の名残。