天天看點

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

繼續閱讀