EduBrick

O. Пересечение окружностей

1000 мс · 256 МБ · всё или ничего

Даны две окружности. Найдите их общие точки.

Формат ввода

В первой строке - число запросов qq (1≤q≤1051 \le q \le 10^5).

В следующих qq строках - по шесть целых чисел: x1x_1, y1y_1, r1r_1, x2x_2, y2y_2, r2r_2. Координаты по модулю не превосходят 10001000, радиусы от 1 до 1000.

Формат вывода

Для каждого запроса выведите −1-1, если общих точек бесконечно много.

Иначе выведите количество точек, а затем сами точки, каждую в отдельной строке, с точностью 10−610^{-6}. Точки упорядочьте по возрастанию xx, при равных xx - по возрастанию yy.

Примеры

ввод
3
0 0 1 3 0 1
0 0 2 3 0 1
0 0 5 0 0 5
вывод
0
1
2 0
-1
ввод
3
0 0 1 1 0 1
0 0 3 0 0 1
0 0 1 0 2 1
вывод
2
0.5 -0.8660254037844386
0.5 0.8660254037844386
0
1
0 1
Разбор идеи от автора задачи. Сначала попробуйте сами.
Войдите, чтобы отправлять решения.