F. Ода строителю мостов
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана двумерная плоскость. Изначально две точки $$$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$$$. Нарисуйте новую точку $$$C$$$ с координатами $$$(x,y)$$$. Затем нарисуйте отрезки $$$AC$$$ и $$$BC$$$, образуя треугольник $$$\triangle ABC$$$.
  • Длина $$$l$$$ каждой стороны нового треугольника $$$\triangle ABC$$$ должна удовлетворять условию $$$0.5\le l\le 1$$$.

Обратите внимание, что каждая операция рисует одну новую точку и два новых отрезка.

Ваша задача — нарисовать точку с координатами $$$(p, q)$$$, используя не более $$$m = \left\lceil 2\sqrt{p^2 + q^2}\right\rceil$$$ операций, где $$$\lceil x\rceil$$$ — это наименьшее целое число, большее или равное $$$x$$$. Гарантируется, что $$$p$$$ и $$$q$$$ — положительные целые числа.

Из-за возможных ошибок округления:

  • Построенная вершина должна находиться в пределах $$$10^{-4}$$$ от $$$(p,q)$$$.
  • Для длин сторон треугольника допускается абсолютная ошибка $$$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$$$ строк, описывающих операции. $$$i$$$-я из следующих $$$n$$$ строк должна содержать четыре значения: два целых числа $$$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$$$. Нарисуйте новую точку $$$P_3$$$ с координатами $$$\left(\frac{1}{2},\frac{\sqrt{3}}{2}\right)$$$. Длины всех сторон треугольника $$$\triangle P_1P_2P_3$$$ равны $$$1$$$.
  2. Выберите точки $$$A = P_2$$$ и $$$B = P_3$$$. Нарисуйте новую точку $$$P_4$$$ с координатами $$$(1, 1)$$$. Длины сторон треугольника $$$\triangle 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]$$$.

Обратите внимание, что последняя операция не является обязательной, и решение все равно будет правильным без последней операции.