CF268C.Beautiful Sets of Points
普及/提高-
通过率:0%
时间限制:1.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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:
- The coordinates of each point in the set are integers.
- 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.
马瑙发明了一个新的数学概念——“优美点集”。他称平面上的一个点集是优美的,当且仅当它满足以下条件:
- 集合中每个点的坐标均为整数;
- 集合中任意两点之间的距离均为非整数。
考虑所有满足如下不等式的点 (x,y):0 ≤ x ≤ n;0 ≤ y ≤ m;x + y > 0。从中选出一个子集,使其规模尽可能大,且该子集本身也是一个优美点集。
输入格式
The single line contains two space-separated integers n and m (1 ≤ n, m ≤ 100).
单行包含两个以空格分隔的整数 n 和 m(1 ≤ n, m ≤ 100)。
输出格式
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.
第一行输出一个整数——所找到的优美集合的大小 k。接下来的 k 行中,每行输出一对以空格分隔的整数——分别为该集合中某个点的 x 坐标和 y 坐标。
若存在多个最优解,输出任意一个即可。
输入输出样例
输入#1
2 2
输出#1
3 0 1 1 2 2 0
输入#2
4 3
输出#2
4 0 3 2 1 3 0 4 2
说明/提示
Consider the first sample. The distance between points (0, 1) and (1, 2) equals
, between (0, 1) and (2, 0) —
, between (1, 2) and (2, 0) —
. Thus, these points form a beautiful set. You cannot form a beautiful set with more than three points out of the given points. Note that this is not the only solution.
考虑第一个样例。点 (0,1) 与 (1,2) 之间的距离为
,点 (0,1) 与 (2,0) 之间的距离为
,点 (1,2) 与 (2,0) 之间的距离为
。因此,这三个点构成一个“优美集合”。在给定的点中,无法选出多于三个点构成优美集合。注意,这并非唯一的解。
输入解题思路,AI测评打分。不知道怎么写?