QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 512 MB Total points: 100

#181. 瘦多边形

Statistics

给定两个整数 $x_{bb}$ 和 $y_{bb}$,你需要找到一个满足以下所有条件的多边形:

  • 顶点数为 3 或 4。
  • 多边形的边不相交也不重叠,即除了端点外,它们不与其他边共享任何点。
  • 每个顶点的 $x$ 和 $y$ 坐标均为整数。
  • 每个顶点的 $x$ 坐标在 $0$ 到 $x_{bb}$ 之间(含边界),$y$ 坐标在 $0$ 到 $y_{bb}$ 之间(含边界)。
  • 至少有一个顶点的 $x$ 坐标为 $0$。
  • 至少有一个顶点的 $x$ 坐标为 $x_{bb}$。
  • 至少有一个顶点的 $y$ 坐标为 $0$。
  • 至少有一个顶点的 $y$ 坐标为 $y_{bb}$。
  • 多边形的面积不超过 $25000$。

该多边形可以是凹多边形。

输入格式

输入包含多个测试用例。第一行包含一个整数 $n$,表示测试用例的数量($1 \le n \le 10^5$)。接下来的 $n$ 行,每行包含一个测试用例,格式如下:

$x_{bb} \ y_{bb}$

其中 $x_{bb}$ 和 $y_{bb}$($2 \le x_{bb} \le 10^9, 2 \le y_{bb} \le 10^9$)为上述整数。

输出格式

对于每个测试用例,按以下格式输出满足上述条件的一个多边形的描述:

$v$ $x_1 \ y_1$ $\vdots$ $x_v \ y_v$

其中 $v$ 是顶点数,每一对 $x_i$ 和 $y_i$ 给出了第 $i$ 个顶点的坐标 $(x_i, y_i)$。第一个顶点 $(x_1, y_1)$ 可以任意选择,其余顶点应按顺时针或逆时针顺序排列。

当有多个多边形满足条件时,输出其中任意一个即可。可以证明,在上述给定的输入范围内,至少存在一个满足条件的多边形。

样例

样例输入 1

2
5 6
1000000000 2

样例输出 1

4
5 6
0 6
0 0
5 0
3
1000000000 0
0 2
999999999 0

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.