Maximum set such that for any two points, the distance is non-integer

Question

I'm trying to solve this problem: http://codeforces.com/problemset/problem/268/C

Manao has invented a new mathematical term — a beautiful set of points. He calls a set of points on a plane beautiful if it meets the following conditions:

1. The coordinates of each point in the set are integers.
2. For any two points from the set, the distance between them is a non-integer.

Consider all points (x, y) which satisfy the inequations: 0 ≤ x ≤ n; 0 ≤ y ≤ m; x + y > 0. Choose their subset of maximum size such that it is also a beautiful set of points.

Input

The single line contains two space-separated integers n and m (1 ≤ n, m ≤ 100).

Output

In the first line print a single integer — the size k of the found beautiful set. In each of the next k lines print a pair of space-separated integers — the x- and y- coordinates, respectively, of a point from the set.

If there are several optimal solutions, you may print any of them.

The solution seems really simple. Like this

#include <cstdio>
main(){
    int i=-1,m,n;
    scanf("%d %d",&m,&n);
    m=(m>n)?n:m;
    printf("%d\n",m+1);
    while(i<m)
        printf("%d %d\n",++i,m-i-1);
}

I can't understand how to arrive at the algorithm. Can you please help? Thanks.

Answer 1

The algorithm basically takes the smaller of m and n, and generates min(m, n) + 1 points whose coordinates are of the form (i, min(m,n) - i) for all i from 0 to min(m, n).

Why does this work? We need to prove 2 things here: the constructed set is beautiful and has maximum size.

1. Consider subsets of all points (x, y), where x and y are integers and 0 <= x <= n and 0 <= y <= m. The maximum size of the subset which is also a beautiful set of points can only be equal or less than min(m, n) + 1.

   This can be easily proven by Pigeonhole Principle. If there are more than min(m, n) + 1 points, then we can find 2 points which the same x or y coordinates and thus having integer distance, which cause the set to fail the beautiful condition.

2. The set of min(m, n) + 1 points of the form (i, min(m,n) - i) for all i from 0 to min(m, n) is a beautiful set of points.

   This is also easy to prove. Choose 2 different points from the set, which will be of the form (a, min(m, n) - a) and (b, min(m, n) - b), where a, b are integers, 0 <= a, b <= min(m, n), a not equal to b. The distance between 2 points will be sqrt((a - b)^ 2 + (b - a)^2) = sqrt(2) * abs(a - b), which is not an integer.

Answer 2

1.

Consider n+1 points in an n*m (n<=m) grid:

(0, n), (1, n-1), (2, n-2) ... (n-1, 1), (n, 0) is always beautiful, whose size is (n+1).

2.

In an n*m (n<=m) grid, you can not have a beautiful point set which is larger than (n+1), otherwise you have to put at least 2 points on the same row/col, so that the distance between them is an integer.

Those two sample outputs look confusing, but they are actually:

3
0 2
1 1
2 0

and

4
0 3
1 2
2 1
3 0