Codeforces 164, C : Beautiful Sets of Points

問題文

http://codeforces.com/contest/268/problem/C

概要

平面上の点について、以下の条件を満たすものを「美しい集合」とする

• 全ての点の座標が整数
• 全ての相異なる二点について、その距離が整数ではない

二つの整数 m, n が与えられる。
かつ かつ なる第一象限の点からなる「美しい集合」に含まれる点の数の最大値 k と、k 個の点の座標を求めよ。

解法

ある格子点に点を置くと、x 座標または y 座標が等しい格子点には点を置けません。
すなわち、使える x 座標、y 座標がそれぞれ 1 減ります。
従って、どう頑張っても max( m, n ) + 1 個しか点を置くことはできません。

max( m, n ) + 1 を k' として、k' 個の点を置くことができるか考えます。
傾き（の絶対値）が 1 の直線上の格子点に点を置くとき、その点の距離は となります。
は無理数であり、無理数の倍数は無理数であるので、これは整数ではありません。
従って、( 0, max( m, n ) ) を通る傾き -1 の直線上の格子点に点を並べることで k' 個の点を置くことができ、k = k' であることが分かります。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n, m;
	cin >> n >> m;

	int k = min( n, m ) + 1;

	cout << k << endl;
	REP( i, 0, k )
	{
		cout << i << ' ' << k - 1 - i << endl;
	}

	return 0;
}