EduBrick

J. Козёл в огороде

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

Огород имеет форму треугольника и не огорожен. Козла привязывают к колышку внутри огорода так, чтобы площадь выпаса была наибольшей, но козёл не заходил на соседние участки. Где вбить колышек и какой длины взять верёвку?

Козёл пасётся в круге. Значит нужен наибольший круг, помещающийся в треугольник, а это вписанная окружность.

Формат ввода

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

В следующих qq строках - по шесть целых чисел: координаты трёх вершин огорода. Координаты по модулю не превосходят 10410^4; точки не лежат на одной прямой.

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

Для каждого запроса выведите три числа: координаты колышка и длину верёвки, с точностью 10−610^{-6}.

Примеры

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