EduBrick

O. Окружность и прямая

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

Окружность задана радиусом rr и центром в начале координат, прямая - уравнением Ax+By+C=0Ax + By + C = 0. Найдите все их общие точки.

Формат ввода

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

В следующих qq строках - по четыре целых числа: rr, AA, BB, CC. Здесь 1≤r≤10001 \le r \le 1000, числа AA, BB, CC по модулю не превосходят 10001000, и AA, BB не равны нулю одновременно.

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

Для каждого запроса выведите в первой строке количество общих точек.

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

Примеры

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