← 返回题目列表

AtCoder · xmascon23_a

A. 艺术不合理

中文机器翻译题面 查看原题

配点 : 100 点

黑兔「今年是 3 选择题!」

白兔「可以用喜欢的尺寸来画画!!」

白兔「……正确答案有几个?」

黑兔「1 個以上」

問題文

k = 2, 3, 4 出 1 请选择,并回答以下问题。

长方形的横向长度与纵向长度的比为 1 : \left(1 + \sqrt[k]{2}\right) 或 至少 \left(1 + \sqrt[k]{2}\right) : 1 的有限个长方形,并且无间隙或重叠地排列,构成一个正方形。更详细的限制请参阅“输出”部分。

可以从此处使用简易可视化工具。


入力

输入为空。

出力

请按以下格式输出。

k
r
n
a_1 b_1 c_1 d_1
a_2 b_2 c_2 d_2
\vdots
a_n b_n c_n d_n
  • k 是你选择的 2, 3, 4 之一。
  • 実数 r 的形式将在后文说明。表示所制作的正方形作为直角坐标平面上的 (0, 0), (r, 0), (r, r), (0, r) 该值应乘以 4 个顶点。
  • n 表示长方形的个数。1 \le n \le 10^5 。 代表
  • 実数 a_i, b_i, c_i, d_i (1 \le i \le n) 的形式将在后文说明。对于第i 个长方形,每个 (a_i, c_i), (b_i, c_i), (b_i, d_i), (a_i, d_i) 该值应乘以 4 个顶点。
  • r 和 a_i, b_i, c_i, d_i (1 \le i \le n) 的k 整数 给出了 p_0, p_1, \ldots, p_{k-1} 用空格分隔输出。其数值为 \sum_{j=0}^{k-1} p_j \left(\sqrt[k]{2}\right)^j 。-10^9 \le p_j \le 10^9 。 代表
  • r > 0 。 代表
  • 各 1 \le i \le n , 定义0 \le a_i < b_i \le r 和 0 \le c_i < d_i \le r 。 代表
  • 各 1 \le i \le n , 定义\dfrac{d_i-c_i}{b_i-a_i} = 1 + \sqrt[k]{2} 或 至少 \dfrac{b_i-a_i}{d_i-c_i} = 1 + \sqrt[k]{2} 。 代表
  • 。正方形的内部及边界的所有点必须包含在 n 个长方形的任意一个内部及边界内,并且n 个长方形的任何 2 内部不应有正面积的公共部分。

入力例 1


出力例 1

4
2 1 1 2
3
0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0
2 0 0 0 2 1 2 1 1 0 0 0 1 1 1 0
0 0 1 0 0 -1 1 2 3 0 0 0 7 -1 -1 2

这就是满足最后条件以外的输出(因此将被判定为错误)。在此例中,长方形如以下图所示排列(左下角坐标为 (0, 0),右下角为 (r, 0) )。

出力例

可以从此处使用简易可视化工具。