← 返回题目列表

Codeforces · 2138/F

F. 桥梁建造者颂歌

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

你有一个 2D 平面。最初,两个点 $$$P_1$$$ 和 $$$P_2$$$ 分别位于 $$$(0,0)$$$ 和 $$$(1,0)$$$ 处,并有一条线段连接它们。您可以使用以下操作绘制三角形:

  • 选择由线段直接连接的两个点 $$$A$$$ 和 $$$B$$$(即 $$$A$$$ 和 $$$B$$$ 必须是现有线段的端点)。
  • 选择两个实数 $$$x$$$ 和 $$$y$$$,使得 $$$-2\cdot 10^4\le x, y\le 2\cdot 10^4$$$。在坐标 $$$(x,y)$$$ 处绘制一个新点 $$$C$$$。然后画线段$$$AC$$$和$$$BC$$$,形成三角形$$$\三角形ABC$$$。
  • 的长度 $$$l$$$ 每 新三角形$$$\triangle ABC$$$的边必须满足$$$0.5\le l\le 1$$$。

请注意,每个操作都会绘制一个新点和两条新线段。

您的任务是使用最多 $$$m = \left\lceil 2\sqrt{p^2 + q^2}\right\rceil$$$ 操作在坐标 $$$(p, q)$$$ 处绘制一个点,其中 $$$\lceil x\rceil$$$ 是大于或等于 $$$x$$$ 的最小整数。保证 $$$p$$$ 和 $$$q$$$ 是正整数。

由于潜在的舍入误差:

  • 构造的顶点只需在 $$$(p,q)$$$ 的 $$$10^{-4}$$$ 范围内。
  • 对于三角形边长,允许绝对误差 $$$10^{-8}$$$(即 $$$0.5 - 10^{-8} \le l \le 1 + 10^{-8}$$$)。

请注意,目标点可能是在最后一次操作之前创建的(请参阅第二个测试用例)。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。

每个测试用例的第一行包含三个整数 $$$p$$$、$$$q$$$ 和 $$$m$$$ ($$$1\le p, q\le 10^4$$$, $$$m = \left\lceil 2\sqrt{p^2 + q^2}\right\rceil$$$) — $$$x$$$ 和分别是目标的 $$$y$$$ 坐标以及允许执行的最大操作数。

保证所有测试用例的 $$$m$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,输出一个整数 $$$n$$$ ($$$0\le n\le m$$$) 表示所使用的操作数。

然后,输出描述操作的 $$$n$$$ 行。接下来的 $$$n$$$ 行的第 $$$i$$$ 应包含四个值:两个整数 $$$u$$$ 和 $$$v$$$ ($$$1\le u,v\le i+1,u\neq v$$$),两个选定点的标识符,后跟两个实数 $$$x$$$ 和 $$$y$$$ ($$$-2\cdot 10^4\le x,y\le 2\cdot 10^4$$$),新点的坐标。

标识符分配如下:

  • 点$$$P_1(0,0)$$$和$$$P_2(1,0)$$$的标识符分别是$$$1$$$和$$$2$$$。
  • 第$$$j$$$操作期间绘制的点的标识符是$$$j+2$$$。

如果存在多个最多使用 $$$m$$$ 操作的有效解,则可以输出其中任何一个。

示例

输入
复制

2
1 1 3
3 1 7

输出
复制

2
1 2 0.5 0.8660254037844386
2 3 1 1
7
1 2 0.5 0.5
2 3 1.1339745962156 0.5
4 2 1.8660254037844 0.5
4 5 2 1
5 6 2.5 0.5
6 7 3 1
6 7 2.5 1

注意

在第一种情况下,您最多可以执行 $$$\lceil 2\sqrt{2}\rceil=3$$$ 操作。以下解决方案仅使用两个操作:

  1. 选择点 $$$A = P_1$$$ 和 $$$B = P_2$$$。在坐标 $$$\left(\frac{1}{2},\frac{\sqrt{3}}{2}\right)$$$ 处绘制一个新点 $$$P_3$$$。三角形$$$\三角形P_1P_2P_3$$$的所有边长均为$$$1$$$。
  2. 选择点 $$$A = P_2$$$ 和 $$$B = P_3$$$。在坐标 $$$(1, 1)$$$ 处绘制一个新点 $$$P_4$$$。三角形 $$$\三角形 P_2P_3P_4$$$ 的边长为 $$$|P_2P_3|=|P_2P_4|=1$$$、$$$|P_3P_4|=2\sin(15^\circ)\approx0.5176\ge 0.5$$$。

在第二种情况下,您最多可以执行 $$$\left\lceil 2\sqrt{10}\right\rceil=7$$$ 操作。

在下面所示的解中,点 $$$P_4$$$ 和 $$$P_5$$$ 分别位于坐标 $$$\left(2-\frac{\sqrt{3}}{2},\frac{1}{2}\right)$$$ 和 $$$\left(1+\frac{\sqrt{3}}{2},\frac{1}{2}\right)$$$ 处,并且$$$|P_4P_6|=|P_2P_5|=1$$$。可以验证每条线段的长度都在$$$[0.5,1]$$$以内。

注意最后一次操作是不必要的,没有最后一次操作解法仍然是正确的。