C. Отрезок в круге

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

Дан круг и отрезок. Найдите длину той части отрезка, которая лежит внутри круга или на его границе.

Формат ввода

В первой строке $q$ ( $1 \le q \le 2 \cdot 10^4$ ). В каждой из следующих $q$ строк семь целых чисел: $x_O$ , $y_O$ , $r$ — центр и радиус круга ( $1 \le r \le 10^4$ ), затем $x_A$ , $y_A$ , $x_B$ , $y_B$ — концы отрезка. Координаты по модулю не превосходят $10^4$ , концы отрезка различны.

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

Для каждого запроса выведите одно число — длину части отрезка внутри круга.

Ответ принимается с абсолютной или относительной погрешностью $10^{-6}$ .

Примеры

ввод

3
0 0 1 -5 0 5 0
0 0 1 0 0 0 3
0 0 2 3 3 5 5

вывод

2.000000000
1.000000000
0.000000000

ввод

2
0 0 5 -5 5 5 5
1 1 3 1 1 2 2

вывод

0.000000000
1.414213562

Разбор идеи от автора задачи. Сначала попробуйте сами.

Войдите, чтобы отправлять решения.