TopCoder SRM 587, Division 1, Level 2 : TriangleXor

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12528&rd=15699

概要

ある正整数 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;
	}
};