配点 : 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) )。
出力例