題目:
若滿足以下條件,就可以說明點是美麗的:
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的正方形的對角線為
),故隻需要找到n與m的最小值k=min(n,m),然後從(0,k)開始循環,確定坐标和是k即可,直到到(k,0),這樣就能保證任意兩個點之間的距離不為整數,因為任意相鄰點都存在
的距離,不相鄰的點之間距離更不為整數,總共有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;
}