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:

  1. The coordinates of each point in the set are integers.
  2. 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.

马瑙发明了一个新的数学概念——“优美点集”。他称平面上的一个点集是优美的,当且仅当它满足以下条件:

  1. 集合中每个点的坐标均为整数;
  2. 集合中任意两点之间的距离均为非整数。

考虑所有满足如下不等式的点 (x, y)(x,\,y):0 ≤ x ≤ n0 \le x \le n;0 ≤ y ≤ m0 \le y \le m;x + y > 0x + y > 0。从中选出一个子集,使其规模尽可能大,且该子集本身也是一个优美点集。

输入格式

The single line contains two space-separated integers n and m (1 ≤ n, m ≤ 100).

单行包含两个以空格分隔的整数 nn 和 mm(1 ≤ n, m ≤ 1001 ≤ 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.

第一行输出一个整数——所找到的优美集合的大小 kk。接下来的 kk 行中,每行输出一对以空格分隔的整数——分别为该集合中某个点的 xx 坐标和 yy 坐标。

若存在多个最优解,输出任意一个即可。

输入输出样例

  • 输入#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)(0, 1) 与 (1,2)(1, 2) 之间的距离为 ,点 (0,1)(0, 1) 与 (2,0)(2, 0) 之间的距离为 ,点 (1,2)(1, 2) 与 (2,0)(2, 0) 之间的距离为 。因此,这三个点构成一个“优美集合”。在给定的点中,无法选出多于三个点构成优美集合。注意,这并非唯一的解。

输入解题思路,AI测评打分。不知道怎么写?

首页