最大集合使得对于任何两点，距离都是非整数

Question

我正在尝试解决这个问题：http : //codeforces.com/problemset/problem/268/C

Manao 发明了一个新的数学术语——一组漂亮的点。如果满足以下条件，他称平面上的一组点是美丽的：

1. 集合中每个点的坐标都是整数。
2. 对于集合中的任意两点，它们之间的距离是非整数。

考虑所有满足不等式的点 (x,?y)：0???x???n; 0???y?m; x?+?y?>?0。选择它们的最大尺寸子集，使其也是一组漂亮的点。

输入

单行包含两个空格分隔的整数 n 和 m (1???n,?m???100)。

输出

在第一行打印一个整数——找到的漂亮集合的大小 k。在接下来的 k 行中的每一行中，打印一对空格分隔的整数——分别是集合中一个点的 x 和 y 坐标。

如果有多个最佳解决方案，您可以打印其中任何一个。

解决方案似乎非常简单。像这样

#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);
}

我无法理解如何得出算法。你能帮忙吗？谢谢。

Answer 1

该算法基本上采用 m 和 n 中的较小者，并为所有从 0 到 min(m, n)。

为什么这样做？我们需要在这里证明两件事：构造的集合是漂亮的并且具有最大尺寸。

1. 考虑所有点 (x, y) 的子集，其中 x 和 y 是整数，并且 0 <= x <= n 和 0 <= y <= m。子集也是一组漂亮的点，其最大大小只能等于或小于 min(m, n) + 1。

   鸽巢原理可以很容易地证明这一点。如果有超过 min(m, n) + 1 个点，那么我们可以找到 2 个具有相同 x 或 y 坐标并因此具有整数距离的点，这会导致集合不符合美观条件。

2. 对于从 0 到 min(m, n) 的所有 i，形式为 (i, min(m,n) - i) 的 min(m, n) + 1 点的集合是一组漂亮的点。

   这也很容易证明。从集合中选择 2 个不同的点，它们的形式为 (a, min(m, n) - a) 和 (b, min(m, n) - b)，其中 a, b 是整数，0 <= a, b <= min(m, n)，a 不等于 b。两点之间的距离为 sqrt((a - b)^ 2 + (b - a)^2) = sqrt(2) * abs(a - b)，它不是整数。