天天看点

codeforces-268C.Beautiful Sets of Points-题解

题目:

若满足以下条件,就可以说明点是美丽的:

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

考虑所有点(x,y)满足(0≤x≤n;0≤y≤m;x + y > 0)选择其最大的子集,使其也是一组漂亮的点。

输入

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

输出

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

如果有几个最优解,可以打印其中任何一个。

例子

输入

2  2

输出

3

0 1

1 2

2 0

(0,1)和(1,2)之间的距离等于(0,1)和(2,0)-之间的距离,(1,2)和(2,0)之间的距离。因此,这些点组成了一个漂亮的集合。你不能在给定的点中形成一个超过3个点的漂亮集合。注意,这不是唯一的解决方案。

思路:

首先定位在两个点之间的距离都不是整数,所以这道题的快速解法与对角线有关(想一想边长为1的正方形的对角线为

codeforces-268C.Beautiful Sets of Points-题解

),故只需要找到n与m的最小值k=min(n,m),然后从(0,k)开始循环,确保坐标和是k即可,直到到(k,0),这样就能保证任意两个点之间的距离不为整数,因为任意相邻点都存在

codeforces-268C.Beautiful Sets of Points-题解

的距离,不相邻的点之间距离更不为整数,总共有k+1个点。

#include<iostream>
#include<cmath> 
using namespace std;
int main() 
{
	int n,m;
	cin>>n>>m;//4 3
	int k;
	k=min(m,n);
	cout<<k+1<<endl;//3
	for(int i=0;i<=k;i++)//2
		cout<<i<<" "<<k-i<<endl;
	return 0;
}
           

继续阅读