概要
ある正整数 W があり、( 0, 0 ), ( 0, 1 ), ( W, 0 ), ( W, 1 ) によって張られる XY 平面がある。
この平面上に、( 0, 1 ), ( W, 1 ), ( x, 0 ) (ただし 0 <= x <= W )によって張られる(中身のある)三角形を描く
奇数個の三角形に被覆されている部分の面積の整数部分を求めよ。
解法
一発で求めるのは難しいので間接的に構成する方法を考えます。
まず、三角形を構成する線分の交点に着目すると、X = 1 の線分を底辺とする三角形が見えます。
それらの面積は交点の Y 座標が分かればすぐに計算することができます。
最初に X = 0 の線分上に頂点をもつ三角形の面積を全て足し合わせます。
そうすると同じ部分を何度も足していて、かつ XOR の結果(問題文中の図で言う)黒になる部分も足されていることになります。
しかし、先程の交点のうち、0 より大きく最小の X をもつ点を頂点とする三角形の面積を適当に引いてやると、黄色い部分の内、X = 0 の線分に接するものの面積のみが残ります。
より上部の段についても同じように計算することで、全体の結果を得ることができます。
コード
#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i ) #include <complex> typedef complex<double> Point; const double EPS = 1e-8; // 外積(クロス積) double cross( const Point &a, const Point &b ) { return a.real() * b.imag() - a.imag() * b.real(); } // 直線 ( p1, p2 ) と直線 ( q1, q2 ) の交点 // include : cross Point intersectionLL( const Point &p1, const Point &p2, const Point &q1, const Point &q2 ) { return p1 + ( p2 - p1 ) * ( cross( q2 - q1, q1 - p1 ) / cross( q2 - q1, p2 - p1 ) ); } class TriangleXor { public: int theArea( int W ) { double res = 0; REP( i, 0, W + 1 ) { res += 1. * W / 2; } REP( i, 1, W + 1 ) { double crossPointY = intersectionLL( Point( 0, 1 ), Point( i, 0 ), Point( W, 1 ), Point( 0, 0 ) ).imag(); res += 1. * W * ( 1. - crossPointY ) * ( i % 2 ? -1 : 1 ) * ( W - i + 1 ); } return res; } };